1 /* Woodstox XML processor
2 *
3 * Copyright (c) 2005 Tatu Saloranta, tatu.saloranta@iki.fi
4 *
5 * Licensed under the License specified in file LICENSE, included with
6 * the source code.
7 * You may not use this file except in compliance with the License.
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 package com.ctc.wstx.util;
17
18 import java.util.*;
19
20 import javax.xml.XMLConstants;
21 import javax.xml.namespace.NamespaceContext;
22
23 import com.ctc.wstx.util.DataUtil;
24
25 /**
26 * Helper class that implements "bijective map" (Map that allows use of values
27 * as keys and vice versa, bidirectional access), and is specifically
28 * used for storing namespace binding information.
29 * One thing worth noting is that Strings stored are NOT assumed to have
30 * been unified (interned) -- if they were, different implementation would
31 * be more optimal.
32 *<p>
33 * Currently only used by stream writers, but could be more generally useful
34 * too.
35 */
36 public final class BijectiveNsMap
37 {
38 /*
39 ///////////////////////////////////////////////
40 // Constants
41 ///////////////////////////////////////////////
42 */
43
44 /**
45 * Let's plan for having up to 14 explicit namespace declarations (2
46 * defaults, for 'xml' and 'xmlns', are pre-populated)
47 */
48 final static int DEFAULT_ARRAY_SIZE = 2 * 16;
49
50 /**
51 * As a simple protection against infinite loops, use an arbitrary but bound
52 * limit for iterators
53 */
54 private final static int MAX_LOOP_FOR_NEW_PREFIX = 999999;
55
56 /*
57 ///////////////////////////////////////////////
58 // Member vars
59 ///////////////////////////////////////////////
60 */
61
62 final int mScopeStart;
63
64 /**
65 * Array that contains { prefix, ns-uri } pairs, up to (but not including)
66 * index {@link #mScopeEnd}.
67 */
68 String[] mNsStrings;
69
70 int mScopeEnd;
71
72 /*
73 ///////////////////////////////////////////////
74 // Life-cycle
75 ///////////////////////////////////////////////
76 */
77
78 private BijectiveNsMap(int scopeStart, String[] strs)
79 {
80 mScopeStart = mScopeEnd = scopeStart;
81 mNsStrings = strs;
82 }
83
84 public static BijectiveNsMap createEmpty()
85 {
86 String[] strs = new String[DEFAULT_ARRAY_SIZE];
87
88 strs[0] = XMLConstants.XML_NS_PREFIX;
89 strs[1] = XMLConstants.XML_NS_URI;
90 strs[2] = XMLConstants.XMLNS_ATTRIBUTE;
91 strs[3] = XMLConstants.XMLNS_ATTRIBUTE_NS_URI;
92
93 // Let's consider pre-defined ones to be 'out of scope', i.e.
94 // conceptually be part of (missing) parent's mappings.
95 return new BijectiveNsMap(4, strs);
96 }
97
98 public BijectiveNsMap createChild() {
99 return new BijectiveNsMap(mScopeEnd, mNsStrings);
100 }
101
102 /*
103 ///////////////////////////////////////////////
104 // Public API, accessors
105 ///////////////////////////////////////////////
106 */
107
108 public String findUriByPrefix(String prefix)
109 {
110 /* This is quite simple: just need to locate the last mapping
111 * for the prefix, if any:
112 */
113 String[] strs = mNsStrings;
114 int phash = prefix.hashCode();
115
116 for (int ix = mScopeEnd - 2; ix >= 0; ix -= 2) {
117 String thisP = strs[ix];
118 if (thisP == prefix ||
119 (thisP.hashCode() == phash && thisP.equals(prefix))) {
120 return strs[ix+1];
121 }
122 }
123 return null;
124 }
125
126 public String findPrefixByUri(String uri)
127 {
128 /* Finding a valid binding for the given URI is trickier, since
129 * mappings can be masked by others... so, we need to first find
130 * most recent binding, from the freshest one, and then verify
131 * it's still unmasked; if not, continue with the first loop,
132 * and so on.
133 */
134
135 String[] strs = mNsStrings;
136 int uhash = uri.hashCode();
137
138 main_loop:
139 for (int ix = mScopeEnd - 1; ix > 0; ix -= 2) {
140 String thisU = strs[ix];
141 if (thisU == uri ||
142 (thisU.hashCode() == uhash && thisU.equals(uri))) {
143 // match, but has it been masked?
144 String prefix = strs[ix-1];
145 /* only need to check, if it wasn't within current scope
146 * (no masking allowed within scopes)
147 */
148 if (ix < mScopeStart) {
149 int phash = prefix.hashCode();
150 for (int j = ix+1, end = mScopeEnd; j < end; j += 2) {
151 String thisP = strs[j];
152 if (thisP == prefix ||
153 (thisP.hashCode() == phash && thisP.equals(prefix))) {
154 // Masking... got to continue the main loop:
155 continue main_loop;
156 }
157 }
158 }
159 // Ok, unmasked one, can return
160 return prefix;
161 }
162 }
163 return null;
164 }
165
166 public List<String> getPrefixesBoundToUri(String uri, List<String> l)
167 {
168 /* Same problems (masking) apply here, as well as with
169 * findPrefixByUri...
170 */
171 String[] strs = mNsStrings;
172 int uhash = uri.hashCode();
173
174 main_loop:
175 for (int ix = mScopeEnd - 1; ix > 0; ix -= 2) {
176 String thisU = strs[ix];
177 if (thisU == uri ||
178 (thisU.hashCode() == uhash && thisU.equals(uri))) {
179 // match, but has it been masked?
180 String prefix = strs[ix-1];
181 /* only need to check, if it wasn't within current scope
182 * (no masking allowed within scopes)
183 */
184 if (ix < mScopeStart) {
185 int phash = prefix.hashCode();
186 for (int j = ix+1, end = mScopeEnd; j < end; j += 2) {
187 String thisP = strs[j];
188 if (thisP == prefix ||
189 (thisP.hashCode() == phash && thisP.equals(prefix))) {
190 // Masking... got to continue the main loop:
191 continue main_loop;
192 }
193 }
194 }
195 // Ok, unmasked one, can add
196 if (l == null) {
197 l = new ArrayList<String>();
198 }
199 l.add(prefix);
200 }
201 }
202 return l;
203 }
204
205 public int size() {
206 return (mScopeEnd >> 1);
207 }
208
209 public int localSize() {
210 return ((mScopeEnd - mScopeStart) >> 1);
211 }
212
213 /*
214 ///////////////////////////////////////////////
215 // Public API, mutators
216 ///////////////////////////////////////////////
217 */
218
219 /**
220 * Method to add a new prefix-to-URI mapping for the current scope.
221 * Note that it should NOT be used for the default namespace
222 * declaration
223 *
224 * @param prefix Prefix to bind
225 * @param uri URI to bind to the prefix
226 *
227 * @return If the prefix was already bound, the URI it was bound to:
228 * null if it's a new binding for the current scope.
229 */
230 public String addMapping(String prefix, String uri)
231 {
232 String[] strs = mNsStrings;
233 int phash = prefix.hashCode();
234
235 for (int ix = mScopeStart, end = mScopeEnd; ix < end; ix += 2) {
236 String thisP = strs[ix];
237 if (thisP == prefix ||
238 (thisP.hashCode() == phash && thisP.equals(prefix))) {
239 // Overriding an existing mapping
240 String old = strs[ix+1];
241 strs[ix+1] = uri;
242 return old;
243 }
244 }
245 // no previous binding, let's just add it at the end
246 if (mScopeEnd >= strs.length) {
247 // let's just double the array sizes...
248 strs = DataUtil.growArrayBy(strs, strs.length);
249 mNsStrings = strs;
250 }
251 strs[mScopeEnd++] = prefix;
252 strs[mScopeEnd++] = uri;
253
254 return null;
255 }
256
257 /**
258 * Method used to add a dynamic binding, and return the prefix
259 * used to bind the specified namespace URI.
260 */
261 public String addGeneratedMapping(String prefixBase, NamespaceContext ctxt,
262 String uri, int[] seqArr)
263 {
264 String[] strs = mNsStrings;
265 int seqNr = seqArr[0];
266 String prefix;
267 int attempts = 0;
268
269 main_loop:
270 while (true) {
271 // We better intern the resulting prefix? Or not?
272 prefix = (prefixBase + seqNr).intern();
273 ++seqNr;
274
275 /* Ok, let's see if we have a mapping (masked or not) for
276 * the prefix. If we do, let's just not use it: we could
277 * of course mask it (unless it's in current scope), but
278 * it's easier to just get a "virgin" prefix...
279 */
280 int phash = prefix.hashCode();
281
282 for (int ix = mScopeEnd - 2; ix >= 0; ix -= 2) {
283 String thisP = strs[ix];
284 if (thisP == prefix ||
285 (thisP.hashCode() == phash && thisP.equals(prefix))) {
286 continue main_loop;
287 }
288 }
289 // So far so good... but do we have a root context that might
290 // have something too?
291
292 // [woodstox-core#74]: had infinite loop for certain Namespace implementations
293 if (ctxt != null) {
294 String existing = ctxt.getNamespaceURI(prefix);
295 if (existing != null && !existing.isEmpty()) {
296 continue;
297 }
298 }
299 // also... guard against infinite loops in general, just in case
300 if (++attempts > MAX_LOOP_FOR_NEW_PREFIX) {
301 throw new IllegalStateException("Internal error: failed to find a mapping prefix for URI '"+uri
302 +" in "+MAX_LOOP_FOR_NEW_PREFIX+" attempts");
303 }
304
305 break;
306 }
307 seqArr[0] = seqNr;
308
309 // Ok, good; then let's just add it in...
310 if (mScopeEnd >= strs.length) {
311 // let's just double the array sizes...
312 strs = DataUtil.growArrayBy(strs, strs.length);
313 mNsStrings = strs;
314 }
315 strs[mScopeEnd++] = prefix;
316 strs[mScopeEnd++] = uri;
317
318 return prefix;
319 }
320
321 /*
322 ///////////////////////////////////////////////
323 // Standard overridden methods
324 ///////////////////////////////////////////////
325 */
326
327 @Override
328 public String toString() {
329 return "["+getClass().toString()+"; "+size()+" entries; of which "
330 +localSize()+" local]";
331 }
332 }
333