1 /*
2  *  Licensed to the Apache Software Foundation (ASF) under one or more
3  *  contributor license agreements.  See the NOTICE file distributed with
4  *  this work for additional information regarding copyright ownership.
5  *  The ASF licenses this file to You under the Apache License, Version 2.0
6  *  (the "License"); you may not use this file except in compliance with
7  *  the License.  You may obtain a copy of the License at
8  *
9  *      http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  */
17 package org.apache.catalina.mapper;
18
19 import java.io.IOException;
20 import java.util.ArrayList;
21 import java.util.Arrays;
22 import java.util.Collection;
23 import java.util.List;
24 import java.util.Map;
25 import java.util.concurrent.ConcurrentHashMap;
26 import java.util.concurrent.CopyOnWriteArrayList;
27
28 import javax.servlet.http.MappingMatch;
29
30 import org.apache.catalina.Context;
31 import org.apache.catalina.Host;
32 import org.apache.catalina.WebResource;
33 import org.apache.catalina.WebResourceRoot;
34 import org.apache.catalina.Wrapper;
35 import org.apache.juli.logging.Log;
36 import org.apache.juli.logging.LogFactory;
37 import org.apache.tomcat.util.buf.Ascii;
38 import org.apache.tomcat.util.buf.CharChunk;
39 import org.apache.tomcat.util.buf.MessageBytes;
40 import org.apache.tomcat.util.res.StringManager;
41
42 /**
43  * Mapper, which implements the servlet API mapping rules (which are derived
44  * from the HTTP rules).
45  *
46  * @author Remy Maucherat
47  */
48 public final class Mapper {
49
50
51     private static final Log log = LogFactory.getLog(Mapper.class);
52
53     private static final StringManager sm = StringManager.getManager(Mapper.class);
54
55     // ----------------------------------------------------- Instance Variables
56
57
58     /**
59      * Array containing the virtual hosts definitions.
60      */
61     // Package private to facilitate testing
62     volatile MappedHost[] hosts = new MappedHost[0];
63
64
65     /**
66      * Default host name.
67      */
68     private volatile String defaultHostName = null;
69     private volatile MappedHost defaultHost = null;
70
71
72     /**
73      * Mapping from Context object to Context version to support
74      * RequestDispatcher mappings.
75      */
76     private final Map<Context, ContextVersion> contextObjectToContextVersionMap =
77             new ConcurrentHashMap<>();
78
79
80     // --------------------------------------------------------- Public Methods
81
82     /**
83      * Set default host.
84      *
85      * @param defaultHostName Default host name
86      */
87     public synchronized void setDefaultHostName(String defaultHostName) {
88         this.defaultHostName = renameWildcardHost(defaultHostName);
89         if (this.defaultHostName == null) {
90             defaultHost = null;
91         } else {
92             defaultHost = exactFind(hosts, this.defaultHostName);
93         }
94     }
95
96
97     /**
98      * Add a new host to the mapper.
99      *
100      * @param name Virtual host name
101      * @param aliases Alias names for the virtual host
102      * @param host Host object
103      */
104     public synchronized void addHost(String name, String[] aliases,
105                                      Host host) {
106         name = renameWildcardHost(name);
107         MappedHost[] newHosts = new MappedHost[hosts.length + 1];
108         MappedHost newHost = new MappedHost(name, host);
109         if (insertMap(hosts, newHosts, newHost)) {
110             hosts = newHosts;
111             if (newHost.name.equals(defaultHostName)) {
112                 defaultHost = newHost;
113             }
114             if (log.isDebugEnabled()) {
115                 log.debug(sm.getString("mapper.addHost.success", name));
116             }
117         } else {
118             MappedHost duplicate = hosts[find(hosts, name)];
119             if (duplicate.object == host) {
120                 // The host is already registered in the mapper.
121                 // E.g. it might have been added by addContextVersion()
122                 if (log.isDebugEnabled()) {
123                     log.debug(sm.getString("mapper.addHost.sameHost", name));
124                 }
125                 newHost = duplicate;
126             } else {
127                 log.error(sm.getString("mapper.duplicateHost", name,
128                         duplicate.getRealHostName()));
129                 // Do not add aliases, as removeHost(hostName) won't be able to
130                 // remove them
131                 return;
132             }
133         }
134         List<MappedHost> newAliases = new ArrayList<>(aliases.length);
135         for (String alias : aliases) {
136             alias = renameWildcardHost(alias);
137             MappedHost newAlias = new MappedHost(alias, newHost);
138             if (addHostAliasImpl(newAlias)) {
139                 newAliases.add(newAlias);
140             }
141         }
142         newHost.addAliases(newAliases);
143     }
144
145
146     /**
147      * Remove a host from the mapper.
148      *
149      * @param name Virtual host name
150      */
151     public synchronized void removeHost(String name) {
152         name = renameWildcardHost(name);
153         // Find and remove the old host
154         MappedHost host = exactFind(hosts, name);
155         if (host == null || host.isAlias()) {
156             return;
157         }
158         MappedHost[] newHosts = hosts.clone();
159         // Remove real host and all its aliases
160         int j = 0;
161         for (int i = 0; i < newHosts.length; i++) {
162             if (newHosts[i].getRealHost() != host) {
163                 newHosts[j++] = newHosts[i];
164             }
165         }
166         hosts = Arrays.copyOf(newHosts, j);
167     }
168
169     /**
170      * Add an alias to an existing host.
171      * @param name  The name of the host
172      * @param alias The alias to add
173      */
174     public synchronized void addHostAlias(String name, String alias) {
175         MappedHost realHost = exactFind(hosts, name);
176         if (realHost == null) {
177             // Should not be adding an alias for a host that doesn't exist but
178             // just in case...
179             return;
180         }
181         alias = renameWildcardHost(alias);
182         MappedHost newAlias = new MappedHost(alias, realHost);
183         if (addHostAliasImpl(newAlias)) {
184             realHost.addAlias(newAlias);
185         }
186     }
187
188     private synchronized boolean addHostAliasImpl(MappedHost newAlias) {
189         MappedHost[] newHosts = new MappedHost[hosts.length + 1];
190         if (insertMap(hosts, newHosts, newAlias)) {
191             hosts = newHosts;
192             if (newAlias.name.equals(defaultHostName)) {
193                 defaultHost = newAlias;
194             }
195             if (log.isDebugEnabled()) {
196                 log.debug(sm.getString("mapper.addHostAlias.success",
197                         newAlias.name, newAlias.getRealHostName()));
198             }
199             return true;
200         } else {
201             MappedHost duplicate = hosts[find(hosts, newAlias.name)];
202             if (duplicate.getRealHost() == newAlias.getRealHost()) {
203                 // A duplicate Alias for the same Host.
204                 // A harmless redundancy. E.g.
205                 // <Host name="localhost"><Alias>localhost</Alias></Host>
206                 if (log.isDebugEnabled()) {
207                     log.debug(sm.getString("mapper.addHostAlias.sameHost",
208                             newAlias.name, newAlias.getRealHostName()));
209                 }
210                 return false;
211             }
212             log.error(sm.getString("mapper.duplicateHostAlias", newAlias.name,
213                     newAlias.getRealHostName(), duplicate.getRealHostName()));
214             return false;
215         }
216     }
217
218     /**
219      * Remove a host alias
220      * @param alias The alias to remove
221      */
222     public synchronized void removeHostAlias(String alias) {
223         alias = renameWildcardHost(alias);
224         // Find and remove the alias
225         MappedHost hostMapping = exactFind(hosts, alias);
226         if (hostMapping == null || !hostMapping.isAlias()) {
227             return;
228         }
229         MappedHost[] newHosts = new MappedHost[hosts.length - 1];
230         if (removeMap(hosts, newHosts, alias)) {
231             hosts = newHosts;
232             hostMapping.getRealHost().removeAlias(hostMapping);
233         }
234
235     }
236
237     /**
238      * Replace {@link MappedHost#contextList} field in <code>realHost</code> and
239      * all its aliases with a new value.
240      */
241     private void updateContextList(MappedHost realHost,
242             ContextList newContextList) {
243
244         realHost.contextList = newContextList;
245         for (MappedHost alias : realHost.getAliases()) {
246             alias.contextList = newContextList;
247         }
248     }
249
250     /**
251      * Add a new Context to an existing Host.
252      *
253      * @param hostName Virtual host name this context belongs to
254      * @param host Host object
255      * @param path Context path
256      * @param version Context version
257      * @param context Context object
258      * @param welcomeResources Welcome files defined for this context
259      * @param resources Static resources of the context
260      * @param wrappers Information on wrapper mappings
261      */
262     public void addContextVersion(String hostName, Host host, String path,
263             String version, Context context, String[] welcomeResources,
264             WebResourceRoot resources, Collection<WrapperMappingInfo> wrappers) {
265
266         hostName = renameWildcardHost(hostName);
267
268         MappedHost mappedHost  = exactFind(hosts, hostName);
269         if (mappedHost == null) {
270             addHost(hostName, new String[0], host);
271             mappedHost = exactFind(hosts, hostName);
272             if (mappedHost == null) {
273                 log.error(sm.getString("mapper.addContext.noHost", hostName));
274                 return;
275             }
276         }
277         if (mappedHost.isAlias()) {
278             log.error(sm.getString("mapper.addContext.hostIsAlias", hostName));
279             return;
280         }
281         int slashCount = slashCount(path);
282         synchronized (mappedHost) {
283             ContextVersion newContextVersion = new ContextVersion(version,
284                     path, slashCount, context, resources, welcomeResources);
285             if (wrappers != null) {
286                 addWrappers(newContextVersion, wrappers);
287             }
288
289             ContextList contextList = mappedHost.contextList;
290             MappedContext mappedContext = exactFind(contextList.contexts, path);
291             if (mappedContext == null) {
292                 mappedContext = new MappedContext(path, newContextVersion);
293                 ContextList newContextList = contextList.addContext(
294                         mappedContext, slashCount);
295                 if (newContextList != null) {
296                     updateContextList(mappedHost, newContextList);
297                     contextObjectToContextVersionMap.put(context, newContextVersion);
298                 }
299             } else {
300                 ContextVersion[] contextVersions = mappedContext.versions;
301                 ContextVersion[] newContextVersions = new ContextVersion[contextVersions.length + 1];
302                 if (insertMap(contextVersions, newContextVersions,
303                         newContextVersion)) {
304                     mappedContext.versions = newContextVersions;
305                     contextObjectToContextVersionMap.put(context, newContextVersion);
306                 } else {
307                     // Re-registration after Context.reload()
308                     // Replace ContextVersion with the new one
309                     int pos = find(contextVersions, version);
310                     if (pos >= 0 && contextVersions[pos].name.equals(version)) {
311                         contextVersions[pos] = newContextVersion;
312                         contextObjectToContextVersionMap.put(context, newContextVersion);
313                     }
314                 }
315             }
316         }
317
318     }
319
320
321     /**
322      * Remove a context from an existing host.
323      *
324      * @param ctxt      The actual context
325      * @param hostName  Virtual host name this context belongs to
326      * @param path      Context path
327      * @param version   Context version
328      */
329     public void removeContextVersion(Context ctxt, String hostName,
330             String path, String version) {
331
332         hostName = renameWildcardHost(hostName);
333         contextObjectToContextVersionMap.remove(ctxt);
334
335         MappedHost host = exactFind(hosts, hostName);
336         if (host == null || host.isAlias()) {
337             return;
338         }
339
340         synchronized (host) {
341             ContextList contextList = host.contextList;
342             MappedContext context = exactFind(contextList.contexts, path);
343             if (context == null) {
344                 return;
345             }
346
347             ContextVersion[] contextVersions = context.versions;
348             ContextVersion[] newContextVersions =
349                 new ContextVersion[contextVersions.length - 1];
350             if (removeMap(contextVersions, newContextVersions, version)) {
351                 if (newContextVersions.length == 0) {
352                     // Remove the context
353                     ContextList newContextList = contextList.removeContext(path);
354                     if (newContextList != null) {
355                         updateContextList(host, newContextList);
356                     }
357                 } else {
358                     context.versions = newContextVersions;
359                 }
360             }
361         }
362     }
363
364
365     /**
366      * Mark a context as being reloaded. Reversion of this state is performed
367      * by calling <code>addContextVersion(...)</code> when context starts up.
368      *
369      * @param ctxt      The actual context
370      * @param hostName  Virtual host name this context belongs to
371      * @param contextPath Context path
372      * @param version   Context version
373      */
374     public void pauseContextVersion(Context ctxt, String hostName,
375             String contextPath, String version) {
376         hostName = renameWildcardHost(hostName);
377         ContextVersion contextVersion = findContextVersion(hostName,
378                 contextPath, version, true);
379         if (contextVersion == null || !ctxt.equals(contextVersion.object)) {
380             return;
381         }
382         contextVersion.markPaused();
383     }
384
385
386     private ContextVersion findContextVersion(String hostName,
387             String contextPath, String version, boolean silent) {
388         MappedHost host = exactFind(hosts, hostName);
389         if (host == null || host.isAlias()) {
390             if (!silent) {
391                 log.error(sm.getString("mapper.findContext.noHostOrAlias", hostName));
392             }
393             return null;
394         }
395         MappedContext context = exactFind(host.contextList.contexts,
396                 contextPath);
397         if (context == null) {
398             if (!silent) {
399                 log.error(sm.getString("mapper.findContext.noContext", contextPath));
400             }
401             return null;
402         }
403         ContextVersion contextVersion = exactFind(context.versions, version);
404         if (contextVersion == null) {
405             if (!silent) {
406                 log.error(sm.getString("mapper.findContext.noContextVersion", contextPath, version));
407             }
408             return null;
409         }
410         return contextVersion;
411     }
412
413
414     public void addWrapper(String hostName, String contextPath, String version,
415                            String path, Wrapper wrapper, boolean jspWildCard,
416                            boolean resourceOnly) {
417         hostName = renameWildcardHost(hostName);
418         ContextVersion contextVersion = findContextVersion(hostName,
419                 contextPath, version, false);
420         if (contextVersion == null) {
421             return;
422         }
423         addWrapper(contextVersion, path, wrapper, jspWildCard, resourceOnly);
424     }
425
426     public void addWrappers(String hostName, String contextPath,
427             String version, Collection<WrapperMappingInfo> wrappers) {
428         hostName = renameWildcardHost(hostName);
429         ContextVersion contextVersion = findContextVersion(hostName,
430                 contextPath, version, false);
431         if (contextVersion == null) {
432             return;
433         }
434         addWrappers(contextVersion, wrappers);
435     }
436
437     /**
438      * Adds wrappers to the given context.
439      *
440      * @param contextVersion The context to which to add the wrappers
441      * @param wrappers Information on wrapper mappings
442      */
443     private void addWrappers(ContextVersion contextVersion,
444             Collection<WrapperMappingInfo> wrappers) {
445         for (WrapperMappingInfo wrapper : wrappers) {
446             addWrapper(contextVersion, wrapper.getMapping(),
447                     wrapper.getWrapper(), wrapper.isJspWildCard(),
448                     wrapper.isResourceOnly());
449         }
450     }
451
452     /**
453      * Adds a wrapper to the given context.
454      *
455      * @param context The context to which to add the wrapper
456      * @param path Wrapper mapping
457      * @param wrapper The Wrapper object
458      * @param jspWildCard true if the wrapper corresponds to the JspServlet
459      *   and the mapping path contains a wildcard; false otherwise
460      * @param resourceOnly true if this wrapper always expects a physical
461      *                     resource to be present (such as a JSP)
462      */
463     protected void addWrapper(ContextVersion context, String path,
464             Wrapper wrapper, boolean jspWildCard, boolean resourceOnly) {
465
466         synchronized (context) {
467             if (path.endsWith("/*")) {
468                 // Wildcard wrapper
469                 String name = path.substring(0, path.length() - 2);
470                 MappedWrapper newWrapper = new MappedWrapper(name, wrapper,
471                         jspWildCard, resourceOnly);
472                 MappedWrapper[] oldWrappers = context.wildcardWrappers;
473                 MappedWrapper[] newWrappers = new MappedWrapper[oldWrappers.length + 1];
474                 if (insertMap(oldWrappers, newWrappers, newWrapper)) {
475                     context.wildcardWrappers = newWrappers;
476                     int slashCount = slashCount(newWrapper.name);
477                     if (slashCount > context.nesting) {
478                         context.nesting = slashCount;
479                     }
480                 }
481             } else if (path.startsWith("*.")) {
482                 // Extension wrapper
483                 String name = path.substring(2);
484                 MappedWrapper newWrapper = new MappedWrapper(name, wrapper,
485                         jspWildCard, resourceOnly);
486                 MappedWrapper[] oldWrappers = context.extensionWrappers;
487                 MappedWrapper[] newWrappers =
488                     new MappedWrapper[oldWrappers.length + 1];
489                 if (insertMap(oldWrappers, newWrappers, newWrapper)) {
490                     context.extensionWrappers = newWrappers;
491                 }
492             } else if (path.equals("/")) {
493                 // Default wrapper
494                 MappedWrapper newWrapper = new MappedWrapper("", wrapper,
495                         jspWildCard, resourceOnly);
496                 context.defaultWrapper = newWrapper;
497             } else {
498                 // Exact wrapper
499                 final String name;
500                 if (path.length() == 0) {
501                     // Special case for the Context Root mapping which is
502                     // treated as an exact match
503                     name = "/";
504                 } else {
505                     name = path;
506                 }
507                 MappedWrapper newWrapper = new MappedWrapper(name, wrapper,
508                         jspWildCard, resourceOnly);
509                 MappedWrapper[] oldWrappers = context.exactWrappers;
510                 MappedWrapper[] newWrappers = new MappedWrapper[oldWrappers.length + 1];
511                 if (insertMap(oldWrappers, newWrappers, newWrapper)) {
512                     context.exactWrappers = newWrappers;
513                 }
514             }
515         }
516     }
517
518
519     /**
520      * Remove a wrapper from an existing context.
521      *
522      * @param hostName    Virtual host name this wrapper belongs to
523      * @param contextPath Context path this wrapper belongs to
524      * @param version     Context version this wrapper belongs to
525      * @param path        Wrapper mapping
526      */
527     public void removeWrapper(String hostName, String contextPath,
528             String version, String path) {
529         hostName = renameWildcardHost(hostName);
530         ContextVersion contextVersion = findContextVersion(hostName,
531                 contextPath, version, true);
532         if (contextVersion == null || contextVersion.isPaused()) {
533             return;
534         }
535         removeWrapper(contextVersion, path);
536     }
537
538     protected void removeWrapper(ContextVersion context, String path) {
539
540         if (log.isDebugEnabled()) {
541             log.debug(sm.getString("mapper.removeWrapper", context.name, path));
542         }
543
544         synchronized (context) {
545             if (path.endsWith("/*")) {
546                 // Wildcard wrapper
547                 String name = path.substring(0, path.length() - 2);
548                 MappedWrapper[] oldWrappers = context.wildcardWrappers;
549                 if (oldWrappers.length == 0) {
550                     return;
551                 }
552                 MappedWrapper[] newWrappers =
553                     new MappedWrapper[oldWrappers.length - 1];
554                 if (removeMap(oldWrappers, newWrappers, name)) {
555                     // Recalculate nesting
556                     context.nesting = 0;
557                     for (int i = 0; i < newWrappers.length; i++) {
558                         int slashCount = slashCount(newWrappers[i].name);
559                         if (slashCount > context.nesting) {
560                             context.nesting = slashCount;
561                         }
562                     }
563                     context.wildcardWrappers = newWrappers;
564                 }
565             } else if (path.startsWith("*.")) {
566                 // Extension wrapper
567                 String name = path.substring(2);
568                 MappedWrapper[] oldWrappers = context.extensionWrappers;
569                 if (oldWrappers.length == 0) {
570                     return;
571                 }
572                 MappedWrapper[] newWrappers =
573                     new MappedWrapper[oldWrappers.length - 1];
574                 if (removeMap(oldWrappers, newWrappers, name)) {
575                     context.extensionWrappers = newWrappers;
576                 }
577             } else if (path.equals("/")) {
578                 // Default wrapper
579                 context.defaultWrapper = null;
580             } else {
581                 // Exact wrapper
582                 String name;
583                 if (path.length() == 0) {
584                     // Special case for the Context Root mapping which is
585                     // treated as an exact match
586                     name = "/";
587                 } else {
588                     name = path;
589                 }
590                 MappedWrapper[] oldWrappers = context.exactWrappers;
591                 if (oldWrappers.length == 0) {
592                     return;
593                 }
594                 MappedWrapper[] newWrappers =
595                     new MappedWrapper[oldWrappers.length - 1];
596                 if (removeMap(oldWrappers, newWrappers, name)) {
597                     context.exactWrappers = newWrappers;
598                 }
599             }
600         }
601     }
602
603
604     /**
605      * Add a welcome file to the given context.
606      *
607      * @param hostName    The host where the given context can be found
608      * @param contextPath The path of the given context
609      * @param version     The version of the given context
610      * @param welcomeFile The welcome file to add
611      */
612     public void addWelcomeFile(String hostName, String contextPath, String version,
613             String welcomeFile) {
614         hostName = renameWildcardHost(hostName);
615         ContextVersion contextVersion = findContextVersion(hostName, contextPath, version, false);
616         if (contextVersion == null) {
617             return;
618         }
619         int len = contextVersion.welcomeResources.length + 1;
620         String[] newWelcomeResources = new String[len];
621         System.arraycopy(contextVersion.welcomeResources, 0, newWelcomeResources, 0, len - 1);
622         newWelcomeResources[len - 1] = welcomeFile;
623         contextVersion.welcomeResources = newWelcomeResources;
624     }
625
626
627     /**
628      * Remove a welcome file from the given context.
629      *
630      * @param hostName    The host where the given context can be found
631      * @param contextPath The path of the given context
632      * @param version     The version of the given context
633      * @param welcomeFile The welcome file to remove
634      */
635     public void removeWelcomeFile(String hostName, String contextPath,
636             String version, String welcomeFile) {
637         hostName = renameWildcardHost(hostName);
638         ContextVersion contextVersion = findContextVersion(hostName, contextPath, version, false);
639         if (contextVersion == null || contextVersion.isPaused()) {
640             return;
641         }
642         int match = -1;
643         for (int i = 0; i < contextVersion.welcomeResources.length; i++) {
644             if (welcomeFile.equals(contextVersion.welcomeResources[i])) {
645                 match = i;
646                 break;
647             }
648         }
649         if (match > -1) {
650             int len = contextVersion.welcomeResources.length - 1;
651             String[] newWelcomeResources = new String[len];
652             System.arraycopy(contextVersion.welcomeResources, 0, newWelcomeResources, 0, match);
653             if (match < len) {
654                 System.arraycopy(contextVersion.welcomeResources, match + 1,
655                         newWelcomeResources, match, len - match);
656             }
657             contextVersion.welcomeResources = newWelcomeResources;
658         }
659     }
660
661
662     /**
663      * Clear the welcome files for the given context.
664      *
665      * @param hostName    The host where the context to be cleared can be found
666      * @param contextPath The path of the context to be cleared
667      * @param version     The version of the context to be cleared
668      */
669     public void clearWelcomeFiles(String hostName, String contextPath, String version) {
670         hostName = renameWildcardHost(hostName);
671         ContextVersion contextVersion = findContextVersion(hostName, contextPath, version, false);
672         if (contextVersion == null) {
673             return;
674         }
675         contextVersion.welcomeResources = new String[0];
676     }
677
678
679     /**
680      * Map the specified host name and URI, mutating the given mapping data.
681      *
682      * @param host Virtual host name
683      * @param uri URI
684      * @param version The version, if any, included in the request to be mapped
685      * @param mappingData This structure will contain the result of the mapping
686      *                    operation
687      * @throws IOException if the buffers are too small to hold the results of
688      *                     the mapping.
689      */
690     public void map(MessageBytes host, MessageBytes uri, String version,
691                     MappingData mappingData) throws IOException {
692
693         if (host.isNull()) {
694             String defaultHostName = this.defaultHostName;
695             if (defaultHostName == null) {
696                 return;
697             }
698             host.getCharChunk().append(defaultHostName);
699         }
700         host.toChars();
701         uri.toChars();
702         internalMap(host.getCharChunk(), uri.getCharChunk(), version, mappingData);
703     }
704
705
706     /**
707      * Map the specified URI relative to the context,
708      * mutating the given mapping data.
709      *
710      * @param context The actual context
711      * @param uri URI
712      * @param mappingData This structure will contain the result of the mapping
713      *                    operation
714      * @throws IOException if the buffers are too small to hold the results of
715      *                     the mapping.
716      */
717     public void map(Context context, MessageBytes uri,
718             MappingData mappingData) throws IOException {
719
720         ContextVersion contextVersion =
721                 contextObjectToContextVersionMap.get(context);
722         uri.toChars();
723         CharChunk uricc = uri.getCharChunk();
724         uricc.setLimit(-1);
725         internalMapWrapper(contextVersion, uricc, mappingData);
726     }
727
728
729     // -------------------------------------------------------- Private Methods
730
731     /**
732      * Map the specified URI.
733      * @throws IOException
734      */
735     @SuppressWarnings("deprecation") // contextPath
736     private final void internalMap(CharChunk host, CharChunk uri,
737             String version, MappingData mappingData) throws IOException {
738
739         if (mappingData.host != null) {
740             // The legacy code (dating down at least to Tomcat 4.1) just
741             // skipped all mapping work in this case. That behaviour has a risk
742             // of returning an inconsistent result.
743             // I do not see a valid use case for it.
744             throw new AssertionError();
745         }
746
747         // Virtual host mapping
748         MappedHost[] hosts = this.hosts;
749         MappedHost mappedHost = exactFindIgnoreCase(hosts, host);
750         if (mappedHost == null) {
751             // Note: Internally, the Mapper does not use the leading * on a
752             //       wildcard host. This is to allow this shortcut.
753             int firstDot = host.indexOf('.');
754             if (firstDot > -1) {
755                 int offset = host.getOffset();
756                 try {
757                     host.setOffset(firstDot + offset);
758                     mappedHost = exactFindIgnoreCase(hosts, host);
759                 } finally {
760                     // Make absolutely sure this gets reset
761                     host.setOffset(offset);
762                 }
763             }
764             if (mappedHost == null) {
765                 mappedHost = defaultHost;
766                 if (mappedHost == null) {
767                     return;
768                 }
769             }
770         }
771         mappingData.host = mappedHost.object;
772
773         if (uri.isNull()) {
774             // Can't map context or wrapper without a uri
775             return;
776         }
777
778         uri.setLimit(-1);
779
780         // Context mapping
781         ContextList contextList = mappedHost.contextList;
782         MappedContext[] contexts = contextList.contexts;
783         int pos = find(contexts, uri);
784         if (pos == -1) {
785             return;
786         }
787
788         int lastSlash = -1;
789         int uriEnd = uri.getEnd();
790         int length = -1;
791         boolean found = false;
792         MappedContext context = null;
793         while (pos >= 0) {
794             context = contexts[pos];
795             if (uri.startsWith(context.name)) {
796                 length = context.name.length();
797                 if (uri.getLength() == length) {
798                     found = true;
799                     break;
800                 } else if (uri.startsWithIgnoreCase("/", length)) {
801                     found = true;
802                     break;
803                 }
804             }
805             if (lastSlash == -1) {
806                 lastSlash = nthSlash(uri, contextList.nesting + 1);
807             } else {
808                 lastSlash = lastSlash(uri);
809             }
810             uri.setEnd(lastSlash);
811             pos = find(contexts, uri);
812         }
813         uri.setEnd(uriEnd);
814
815         if (!found) {
816             if (contexts[0].name.equals("")) {
817                 context = contexts[0];
818             } else {
819                 context = null;
820             }
821         }
822         if (context == null) {
823             return;
824         }
825
826         mappingData.contextPath.setString(context.name);
827
828         ContextVersion contextVersion = null;
829         ContextVersion[] contextVersions = context.versions;
830         final int versionCount = contextVersions.length;
831         if (versionCount > 1) {
832             Context[] contextObjects = new Context[contextVersions.length];
833             for (int i = 0; i < contextObjects.length; i++) {
834                 contextObjects[i] = contextVersions[i].object;
835             }
836             mappingData.contexts = contextObjects;
837             if (version != null) {
838                 contextVersion = exactFind(contextVersions, version);
839             }
840         }
841         if (contextVersion == null) {
842             // Return the latest version
843             // The versions array is known to contain at least one element
844             contextVersion = contextVersions[versionCount - 1];
845         }
846         mappingData.context = contextVersion.object;
847         mappingData.contextSlashCount = contextVersion.slashCount;
848
849         // Wrapper mapping
850         if (!contextVersion.isPaused()) {
851             internalMapWrapper(contextVersion, uri, mappingData);
852         }
853
854     }
855
856
857     /**
858      * Wrapper mapping.
859      * @throws IOException if the buffers are too small to hold the results of
860      *                     the mapping.
861      */
862     private final void internalMapWrapper(ContextVersion contextVersion,
863                                           CharChunk path,
864                                           MappingData mappingData) throws IOException {
865
866         int pathOffset = path.getOffset();
867         int pathEnd = path.getEnd();
868         boolean noServletPath = false;
869
870         int length = contextVersion.path.length();
871         if (length == (pathEnd - pathOffset)) {
872             noServletPath = true;
873         }
874         int servletPath = pathOffset + length;
875         path.setOffset(servletPath);
876
877         // Rule 1 -- Exact Match
878         MappedWrapper[] exactWrappers = contextVersion.exactWrappers;
879         internalMapExactWrapper(exactWrappers, path, mappingData);
880
881         // Rule 2 -- Prefix Match
882         boolean checkJspWelcomeFiles = false;
883         MappedWrapper[] wildcardWrappers = contextVersion.wildcardWrappers;
884         if (mappingData.wrapper == null) {
885             internalMapWildcardWrapper(wildcardWrappers, contextVersion.nesting,
886                                        path, mappingData);
887             if (mappingData.wrapper != null && mappingData.jspWildCard) {
888                 char[] buf = path.getBuffer();
889                 if (buf[pathEnd - 1] == '/') {
890                     /*
891                      * Path ending in '/' was mapped to JSP servlet based on
892                      * wildcard match (e.g., as specified in url-pattern of a
893                      * jsp-property-group.
894                      * Force the context's welcome files, which are interpreted
895                      * as JSP files (since they match the url-pattern), to be
896                      * considered. See Bugzilla 27664.
897                      */
898                     mappingData.wrapper = null;
899                     checkJspWelcomeFiles = true;
900                 } else {
901                     // See Bugzilla 27704
902                     mappingData.wrapperPath.setChars(buf, path.getStart(),
903                                                      path.getLength());
904                     mappingData.pathInfo.recycle();
905                 }
906             }
907         }
908
909         if(mappingData.wrapper == null && noServletPath &&
910                 contextVersion.object.getMapperContextRootRedirectEnabled()) {
911             // The path is empty, redirect to "/"
912             path.append('/');
913             pathEnd = path.getEnd();
914             mappingData.redirectPath.setChars
915                 (path.getBuffer(), pathOffset, pathEnd - pathOffset);
916             path.setEnd(pathEnd - 1);
917             return;
918         }
919
920         // Rule 3 -- Extension Match
921         MappedWrapper[] extensionWrappers = contextVersion.extensionWrappers;
922         if (mappingData.wrapper == null && !checkJspWelcomeFiles) {
923             internalMapExtensionWrapper(extensionWrappers, path, mappingData,
924                     true);
925         }
926
927         // Rule 4 -- Welcome resources processing for servlets
928         if (mappingData.wrapper == null) {
929             boolean checkWelcomeFiles = checkJspWelcomeFiles;
930             if (!checkWelcomeFiles) {
931                 char[] buf = path.getBuffer();
932                 checkWelcomeFiles = (buf[pathEnd - 1] == '/');
933             }
934             if (checkWelcomeFiles) {
935                 for (int i = 0; (i < contextVersion.welcomeResources.length)
936                          && (mappingData.wrapper == null); i++) {
937                     path.setOffset(pathOffset);
938                     path.setEnd(pathEnd);
939                     path.append(contextVersion.welcomeResources[i], 0,
940                             contextVersion.welcomeResources[i].length());
941                     path.setOffset(servletPath);
942
943                     // Rule 4a -- Welcome resources processing for exact macth
944                     internalMapExactWrapper(exactWrappers, path, mappingData);
945
946                     // Rule 4b -- Welcome resources processing for prefix match
947                     if (mappingData.wrapper == null) {
948                         internalMapWildcardWrapper
949                             (wildcardWrappers, contextVersion.nesting,
950                              path, mappingData);
951                     }
952
953                     // Rule 4c -- Welcome resources processing
954                     //            for physical folder
955                     if (mappingData.wrapper == null
956                         && contextVersion.resources != null) {
957                         String pathStr = path.toString();
958                         WebResource file =
959                                 contextVersion.resources.getResource(pathStr);
960                         if (file != null && file.isFile()) {
961                             internalMapExtensionWrapper(extensionWrappers, path,
962                                                         mappingData, true);
963                             if (mappingData.wrapper == null
964                                 && contextVersion.defaultWrapper != null) {
965                                 mappingData.wrapper =
966                                     contextVersion.defaultWrapper.object;
967                                 mappingData.requestPath.setChars
968                                     (path.getBuffer(), path.getStart(),
969                                      path.getLength());
970                                 mappingData.wrapperPath.setChars
971                                     (path.getBuffer(), path.getStart(),
972                                      path.getLength());
973                                 mappingData.requestPath.setString(pathStr);
974                                 mappingData.wrapperPath.setString(pathStr);
975                             }
976                         }
977                     }
978                 }
979
980                 path.setOffset(servletPath);
981                 path.setEnd(pathEnd);
982             }
983
984         }
985
986         /* welcome file processing - take 2
987          * Now that we have looked for welcome files with a physical
988          * backing, now look for an extension mapping listed
989          * but may not have a physical backing to it. This is for
990          * the case of index.jsf, index.do, etc.
991          * A watered down version of rule 4
992          */
993         if (mappingData.wrapper == null) {
994             boolean checkWelcomeFiles = checkJspWelcomeFiles;
995             if (!checkWelcomeFiles) {
996                 char[] buf = path.getBuffer();
997                 checkWelcomeFiles = (buf[pathEnd - 1] == '/');
998             }
999             if (checkWelcomeFiles) {
1000                 for (int i = 0; (i < contextVersion.welcomeResources.length)
1001                          && (mappingData.wrapper == null); i++) {
1002                     path.setOffset(pathOffset);
1003                     path.setEnd(pathEnd);
1004                     path.append(contextVersion.welcomeResources[i], 0,
1005                                 contextVersion.welcomeResources[i].length());
1006                     path.setOffset(servletPath);
1007                     internalMapExtensionWrapper(extensionWrappers, path,
1008                                                 mappingData, false);
1009                 }
1010
1011                 path.setOffset(servletPath);
1012                 path.setEnd(pathEnd);
1013             }
1014         }
1015
1016
1017         // Rule 7 -- Default servlet
1018         if (mappingData.wrapper == null && !checkJspWelcomeFiles) {
1019             if (contextVersion.defaultWrapper != null) {
1020                 mappingData.wrapper = contextVersion.defaultWrapper.object;
1021                 mappingData.requestPath.setChars
1022                     (path.getBuffer(), path.getStart(), path.getLength());
1023                 mappingData.wrapperPath.setChars
1024                     (path.getBuffer(), path.getStart(), path.getLength());
1025                 mappingData.matchType = MappingMatch.DEFAULT;
1026             }
1027             // Redirection to a folder
1028             char[] buf = path.getBuffer();
1029             if (contextVersion.resources != null && buf[pathEnd -1 ] != '/') {
1030                 String pathStr = path.toString();
1031                 // Note: Check redirect first to save unnecessary getResource()
1032                 //       call. See BZ 62968.
1033                 if (contextVersion.object.getMapperDirectoryRedirectEnabled()) {
1034                     WebResource file;
1035                     // Handle context root
1036                     if (pathStr.length() == 0) {
1037                         file = contextVersion.resources.getResource("/");
1038                     } else {
1039                         file = contextVersion.resources.getResource(pathStr);
1040                     }
1041                     if (file != null && file.isDirectory()) {
1042                         // Note: this mutates the path: do not do any processing
1043                         // after this (since we set the redirectPath, there
1044                         // shouldn't be any)
1045                         path.setOffset(pathOffset);
1046                         path.append('/');
1047                         mappingData.redirectPath.setChars
1048                             (path.getBuffer(), path.getStart(), path.getLength());
1049                     } else {
1050                         mappingData.requestPath.setString(pathStr);
1051                         mappingData.wrapperPath.setString(pathStr);
1052                     }
1053                 } else {
1054                     mappingData.requestPath.setString(pathStr);
1055                     mappingData.wrapperPath.setString(pathStr);
1056                 }
1057             }
1058         }
1059
1060         path.setOffset(pathOffset);
1061         path.setEnd(pathEnd);
1062     }
1063
1064
1065     /**
1066      * Exact mapping.
1067      */
1068     @SuppressWarnings("deprecation") // contextPath
1069     private final void internalMapExactWrapper
1070         (MappedWrapper[] wrappers, CharChunk path, MappingData mappingData) {
1071         MappedWrapper wrapper = exactFind(wrappers, path);
1072         if (wrapper != null) {
1073             mappingData.requestPath.setString(wrapper.name);
1074             mappingData.wrapper = wrapper.object;
1075             if (path.equals("/")) {
1076                 // Special handling for Context Root mapped servlet
1077                 mappingData.pathInfo.setString("/");
1078                 mappingData.wrapperPath.setString("");
1079                 // This seems wrong but it is what the spec says...
1080                 mappingData.contextPath.setString("");
1081                 mappingData.matchType = MappingMatch.CONTEXT_ROOT;
1082             } else {
1083                 mappingData.wrapperPath.setString(wrapper.name);
1084                 mappingData.matchType = MappingMatch.EXACT;
1085             }
1086         }
1087     }
1088
1089
1090     /**
1091      * Wildcard mapping.
1092      */
1093     private final void internalMapWildcardWrapper
1094         (MappedWrapper[] wrappers, int nesting, CharChunk path,
1095          MappingData mappingData) {
1096
1097         int pathEnd = path.getEnd();
1098
1099         int lastSlash = -1;
1100         int length = -1;
1101         int pos = find(wrappers, path);
1102         if (pos != -1) {
1103             boolean found = false;
1104             while (pos >= 0) {
1105                 if (path.startsWith(wrappers[pos].name)) {
1106                     length = wrappers[pos].name.length();
1107                     if (path.getLength() == length) {
1108                         found = true;
1109                         break;
1110                     } else if (path.startsWithIgnoreCase("/", length)) {
1111                         found = true;
1112                         break;
1113                     }
1114                 }
1115                 if (lastSlash == -1) {
1116                     lastSlash = nthSlash(path, nesting + 1);
1117                 } else {
1118                     lastSlash = lastSlash(path);
1119                 }
1120                 path.setEnd(lastSlash);
1121                 pos = find(wrappers, path);
1122             }
1123             path.setEnd(pathEnd);
1124             if (found) {
1125                 mappingData.wrapperPath.setString(wrappers[pos].name);
1126                 if (path.getLength() > length) {
1127                     mappingData.pathInfo.setChars
1128                         (path.getBuffer(),
1129                          path.getOffset() + length,
1130                          path.getLength() - length);
1131                 }
1132                 mappingData.requestPath.setChars
1133                     (path.getBuffer(), path.getOffset(), path.getLength());
1134                 mappingData.wrapper = wrappers[pos].object;
1135                 mappingData.jspWildCard = wrappers[pos].jspWildCard;
1136                 mappingData.matchType = MappingMatch.PATH;
1137             }
1138         }
1139     }
1140
1141
1142     /**
1143      * Extension mappings.
1144      *
1145      * @param wrappers          Set of wrappers to check for matches
1146      * @param path              Path to map
1147      * @param mappingData       Mapping data for result
1148      * @param resourceExpected  Is this mapping expecting to find a resource
1149      */
1150     private final void internalMapExtensionWrapper(MappedWrapper[] wrappers,
1151             CharChunk path, MappingData mappingData, boolean resourceExpected) {
1152         char[] buf = path.getBuffer();
1153         int pathEnd = path.getEnd();
1154         int servletPath = path.getOffset();
1155         int slash = -1;
1156         for (int i = pathEnd - 1; i >= servletPath; i--) {
1157             if (buf[i] == '/') {
1158                 slash = i;
1159                 break;
1160             }
1161         }
1162         if (slash >= 0) {
1163             int period = -1;
1164             for (int i = pathEnd - 1; i > slash; i--) {
1165                 if (buf[i] == '.') {
1166                     period = i;
1167                     break;
1168                 }
1169             }
1170             if (period >= 0) {
1171                 path.setOffset(period + 1);
1172                 path.setEnd(pathEnd);
1173                 MappedWrapper wrapper = exactFind(wrappers, path);
1174                 if (wrapper != null
1175                         && (resourceExpected || !wrapper.resourceOnly)) {
1176                     mappingData.wrapperPath.setChars(buf, servletPath, pathEnd
1177                             - servletPath);
1178                     mappingData.requestPath.setChars(buf, servletPath, pathEnd
1179                             - servletPath);
1180                     mappingData.wrapper = wrapper.object;
1181                     mappingData.matchType = MappingMatch.EXTENSION;
1182                 }
1183                 path.setOffset(servletPath);
1184                 path.setEnd(pathEnd);
1185             }
1186         }
1187     }
1188
1189
1190     /**
1191      * Find a map element given its name in a sorted array of map elements.
1192      * This will return the index for the closest inferior or equal item in the
1193      * given array.
1194      */
1195     private static final <T> int find(MapElement<T>[] map, CharChunk name) {
1196         return find(map, name, name.getStart(), name.getEnd());
1197     }
1198
1199
1200     /**
1201      * Find a map element given its name in a sorted array of map elements.
1202      * This will return the index for the closest inferior or equal item in the
1203      * given array.
1204      */
1205     private static final <T> int find(MapElement<T>[] map, CharChunk name,
1206                                   int start, int end) {
1207
1208         int a = 0;
1209         int b = map.length - 1;
1210
1211         // Special cases: -1 and 0
1212         if (b == -1) {
1213             return -1;
1214         }
1215
1216         if (compare(name, start, end, map[0].name) < 0 ) {
1217             return -1;
1218         }
1219         if (b == 0) {
1220             return 0;
1221         }
1222
1223         int i = 0;
1224         while (true) {
1225             i = (b + a) >>> 1;
1226             int result = compare(name, start, end, map[i].name);
1227             if (result == 1) {
1228                 a = i;
1229             } else if (result == 0) {
1230                 return i;
1231             } else {
1232                 b = i;
1233             }
1234             if ((b - a) == 1) {
1235                 int result2 = compare(name, start, end, map[b].name);
1236                 if (result2 < 0) {
1237                     return a;
1238                 } else {
1239                     return b;
1240                 }
1241             }
1242         }
1243
1244     }
1245
1246     /**
1247      * Find a map element given its name in a sorted array of map elements.
1248      * This will return the index for the closest inferior or equal item in the
1249      * given array.
1250      */
1251     private static final <T> int findIgnoreCase(MapElement<T>[] map, CharChunk name) {
1252         return findIgnoreCase(map, name, name.getStart(), name.getEnd());
1253     }
1254
1255
1256     /**
1257      * Find a map element given its name in a sorted array of map elements.
1258      * This will return the index for the closest inferior or equal item in the
1259      * given array.
1260      */
1261     private static final <T> int findIgnoreCase(MapElement<T>[] map, CharChunk name,
1262                                   int start, int end) {
1263
1264         int a = 0;
1265         int b = map.length - 1;
1266
1267         // Special cases: -1 and 0
1268         if (b == -1) {
1269             return -1;
1270         }
1271         if (compareIgnoreCase(name, start, end, map[0].name) < 0 ) {
1272             return -1;
1273         }
1274         if (b == 0) {
1275             return 0;
1276         }
1277
1278         int i = 0;
1279         while (true) {
1280             i = (b + a) >>> 1;
1281             int result = compareIgnoreCase(name, start, end, map[i].name);
1282             if (result == 1) {
1283                 a = i;
1284             } else if (result == 0) {
1285                 return i;
1286             } else {
1287                 b = i;
1288             }
1289             if ((b - a) == 1) {
1290                 int result2 = compareIgnoreCase(name, start, end, map[b].name);
1291                 if (result2 < 0) {
1292                     return a;
1293                 } else {
1294                     return b;
1295                 }
1296             }
1297         }
1298
1299     }
1300
1301
1302     /**
1303      * Find a map element given its name in a sorted array of map elements.
1304      * This will return the index for the closest inferior or equal item in the
1305      * given array.
1306      * @see #exactFind(MapElement[], String)
1307      */
1308     private static final <T> int find(MapElement<T>[] map, String name) {
1309
1310         int a = 0;
1311         int b = map.length - 1;
1312
1313         // Special cases: -1 and 0
1314         if (b == -1) {
1315             return -1;
1316         }
1317
1318         if (name.compareTo(map[0].name) < 0) {
1319             return -1;
1320         }
1321         if (b == 0) {
1322             return 0;
1323         }
1324
1325         int i = 0;
1326         while (true) {
1327             i = (b + a) >>> 1;
1328             int result = name.compareTo(map[i].name);
1329             if (result > 0) {
1330                 a = i;
1331             } else if (result == 0) {
1332                 return i;
1333             } else {
1334                 b = i;
1335             }
1336             if ((b - a) == 1) {
1337                 int result2 = name.compareTo(map[b].name);
1338                 if (result2 < 0) {
1339                     return a;
1340                 } else {
1341                     return b;
1342                 }
1343             }
1344         }
1345
1346     }
1347
1348
1349     /**
1350      * Find a map element given its name in a sorted array of map elements. This
1351      * will return the element that you were searching for. Otherwise it will
1352      * return <code>null</code>.
1353      * @see #find(MapElement[], String)
1354      */
1355     private static final <T, E extends MapElement<T>> E exactFind(E[] map,
1356             String name) {
1357         int pos = find(map, name);
1358         if (pos >= 0) {
1359             E result = map[pos];
1360             if (name.equals(result.name)) {
1361                 return result;
1362             }
1363         }
1364         return null;
1365     }
1366
1367     /**
1368      * Find a map element given its name in a sorted array of map elements. This
1369      * will return the element that you were searching for. Otherwise it will
1370      * return <code>null</code>.
1371      */
1372     private static final <T, E extends MapElement<T>> E exactFind(E[] map,
1373             CharChunk name) {
1374         int pos = find(map, name);
1375         if (pos >= 0) {
1376             E result = map[pos];
1377             if (name.equals(result.name)) {
1378                 return result;
1379             }
1380         }
1381         return null;
1382     }
1383
1384     /**
1385      * Find a map element given its name in a sorted array of map elements. This
1386      * will return the element that you were searching for. Otherwise it will
1387      * return <code>null</code>.
1388      * @see #findIgnoreCase(MapElement[], CharChunk)
1389      */
1390     private static final <T, E extends MapElement<T>> E exactFindIgnoreCase(
1391             E[] map, CharChunk name) {
1392         int pos = findIgnoreCase(map, name);
1393         if (pos >= 0) {
1394             E result = map[pos];
1395             if (name.equalsIgnoreCase(result.name)) {
1396                 return result;
1397             }
1398         }
1399         return null;
1400     }
1401
1402
1403     /**
1404      * Compare given char chunk with String.
1405      * Return -1, 0 or +1 if inferior, equal, or superior to the String.
1406      */
1407     private static final int compare(CharChunk name, int start, int end,
1408                                      String compareTo) {
1409         int result = 0;
1410         char[] c = name.getBuffer();
1411         int len = compareTo.length();
1412         if ((end - start) < len) {
1413             len = end - start;
1414         }
1415         for (int i = 0; (i < len) && (result == 0); i++) {
1416             if (c[i + start] > compareTo.charAt(i)) {
1417                 result = 1;
1418             } else if (c[i + start] < compareTo.charAt(i)) {
1419                 result = -1;
1420             }
1421         }
1422         if (result == 0) {
1423             if (compareTo.length() > (end - start)) {
1424                 result = -1;
1425             } else if (compareTo.length() < (end - start)) {
1426                 result = 1;
1427             }
1428         }
1429         return result;
1430     }
1431
1432
1433     /**
1434      * Compare given char chunk with String ignoring case.
1435      * Return -1, 0 or +1 if inferior, equal, or superior to the String.
1436      */
1437     private static final int compareIgnoreCase(CharChunk name, int start, int end,
1438                                      String compareTo) {
1439         int result = 0;
1440         char[] c = name.getBuffer();
1441         int len = compareTo.length();
1442         if ((end - start) < len) {
1443             len = end - start;
1444         }
1445         for (int i = 0; (i < len) && (result == 0); i++) {
1446             if (Ascii.toLower(c[i + start]) > Ascii.toLower(compareTo.charAt(i))) {
1447                 result = 1;
1448             } else if (Ascii.toLower(c[i + start]) < Ascii.toLower(compareTo.charAt(i))) {
1449                 result = -1;
1450             }
1451         }
1452         if (result == 0) {
1453             if (compareTo.length() > (end - start)) {
1454                 result = -1;
1455             } else if (compareTo.length() < (end - start)) {
1456                 result = 1;
1457             }
1458         }
1459         return result;
1460     }
1461
1462
1463     /**
1464      * Find the position of the last slash in the given char chunk.
1465      */
1466     private static final int lastSlash(CharChunk name) {
1467         char[] c = name.getBuffer();
1468         int end = name.getEnd();
1469         int start = name.getStart();
1470         int pos = end;
1471
1472         while (pos > start) {
1473             if (c[--pos] == '/') {
1474                 break;
1475             }
1476         }
1477
1478         return pos;
1479     }
1480
1481
1482     /**
1483      * Find the position of the nth slash, in the given char chunk.
1484      */
1485     private static final int nthSlash(CharChunk name, int n) {
1486         char[] c = name.getBuffer();
1487         int end = name.getEnd();
1488         int start = name.getStart();
1489         int pos = start;
1490         int count = 0;
1491
1492         while (pos < end) {
1493             if ((c[pos++] == '/') && ((++count) == n)) {
1494                 pos--;
1495                 break;
1496             }
1497         }
1498
1499         return pos;
1500     }
1501
1502
1503     /**
1504      * Return the slash count in a given string.
1505      */
1506     private static final int slashCount(String name) {
1507         int pos = -1;
1508         int count = 0;
1509         while ((pos = name.indexOf('/', pos + 1)) != -1) {
1510             count++;
1511         }
1512         return count;
1513     }
1514
1515
1516     /**
1517      * Insert into the right place in a sorted MapElement array, and prevent
1518      * duplicates.
1519      */
1520     private static final <T> boolean insertMap
1521         (MapElement<T>[] oldMap, MapElement<T>[] newMap, MapElement<T> newElement) {
1522         int pos = find(oldMap, newElement.name);
1523         if ((pos != -1) && (newElement.name.equals(oldMap[pos].name))) {
1524             return false;
1525         }
1526         System.arraycopy(oldMap, 0, newMap, 0, pos + 1);
1527         newMap[pos + 1] = newElement;
1528         System.arraycopy
1529             (oldMap, pos + 1, newMap, pos + 2, oldMap.length - pos - 1);
1530         return true;
1531     }
1532
1533
1534     /**
1535      * Insert into the right place in a sorted MapElement array.
1536      */
1537     private static final <T> boolean removeMap
1538         (MapElement<T>[] oldMap, MapElement<T>[] newMap, String name) {
1539         int pos = find(oldMap, name);
1540         if ((pos != -1) && (name.equals(oldMap[pos].name))) {
1541             System.arraycopy(oldMap, 0, newMap, 0, pos);
1542             System.arraycopy(oldMap, pos + 1, newMap, pos,
1543                              oldMap.length - pos - 1);
1544             return true;
1545         }
1546         return false;
1547     }
1548
1549
1550     /*
1551      * To simplify the mapping process, wild card hosts take the form
1552      * ".apache.org" rather than "*.apache.org" internally. However, for ease
1553      * of use the external form remains "*.apache.org". Any host name passed
1554      * into this class needs to be passed through this method to rename and
1555      * wild card host names from the external to internal form.
1556      */
1557     private static String renameWildcardHost(String hostName) {
1558         if (hostName != null && hostName.startsWith("*.")) {
1559             return hostName.substring(1);
1560         } else {
1561             return hostName;
1562         }
1563     }
1564
1565
1566     // ------------------------------------------------- MapElement Inner Class
1567
1568
1569     protected abstract static class MapElement<T> {
1570
1571         public final String name;
1572         public final T object;
1573
1574         public MapElement(String name, T object) {
1575             this.name = name;
1576             this.object = object;
1577         }
1578     }
1579
1580
1581     // ------------------------------------------------------- Host Inner Class
1582
1583
1584     protected static final class MappedHost extends MapElement<Host> {
1585
1586         public volatile ContextList contextList;
1587
1588         /**
1589          * Link to the "real" MappedHost, shared by all aliases.
1590          */
1591         private final MappedHost realHost;
1592
1593         /**
1594          * Links to all registered aliases, for easy enumeration. This field
1595          * is available only in the "real" MappedHost. In an alias this field
1596          * is <code>null</code>.
1597          */
1598         private final List<MappedHost> aliases;
1599
1600         /**
1601          * Constructor used for the primary Host
1602          *
1603          * @param name The name of the virtual host
1604          * @param host The host
1605          */
1606         public MappedHost(String name, Host host) {
1607             super(name, host);
1608             realHost = this;
1609             contextList = new ContextList();
1610             aliases = new CopyOnWriteArrayList<>();
1611         }
1612
1613         /**
1614          * Constructor used for an Alias
1615          *
1616          * @param alias    The alias of the virtual host
1617          * @param realHost The host the alias points to
1618          */
1619         public MappedHost(String alias, MappedHost realHost) {
1620             super(alias, realHost.object);
1621             this.realHost = realHost;
1622             this.contextList = realHost.contextList;
1623             this.aliases = null;
1624         }
1625
1626         public boolean isAlias() {
1627             return realHost != this;
1628         }
1629
1630         public MappedHost getRealHost() {
1631             return realHost;
1632         }
1633
1634         public String getRealHostName() {
1635             return realHost.name;
1636         }
1637
1638         public Collection<MappedHost> getAliases() {
1639             return aliases;
1640         }
1641
1642         public void addAlias(MappedHost alias) {
1643             aliases.add(alias);
1644         }
1645
1646         public void addAliases(Collection<? extends MappedHost> c) {
1647             aliases.addAll(c);
1648         }
1649
1650         public void removeAlias(MappedHost alias) {
1651             aliases.remove(alias);
1652         }
1653     }
1654
1655
1656     // ------------------------------------------------ ContextList Inner Class
1657
1658
1659     protected static final class ContextList {
1660
1661         public final MappedContext[] contexts;
1662         public final int nesting;
1663
1664         public ContextList() {
1665             this(new MappedContext[0], 0);
1666         }
1667
1668         private ContextList(MappedContext[] contexts, int nesting) {
1669             this.contexts = contexts;
1670             this.nesting = nesting;
1671         }
1672
1673         public ContextList addContext(MappedContext mappedContext,
1674                 int slashCount) {
1675             MappedContext[] newContexts = new MappedContext[contexts.length + 1];
1676             if (insertMap(contexts, newContexts, mappedContext)) {
1677                 return new ContextList(newContexts, Math.max(nesting,
1678                         slashCount));
1679             }
1680             return null;
1681         }
1682
1683         public ContextList removeContext(String path) {
1684             MappedContext[] newContexts = new MappedContext[contexts.length - 1];
1685             if (removeMap(contexts, newContexts, path)) {
1686                 int newNesting = 0;
1687                 for (MappedContext context : newContexts) {
1688                     newNesting = Math.max(newNesting, slashCount(context.name));
1689                 }
1690                 return new ContextList(newContexts, newNesting);
1691             }
1692             return null;
1693         }
1694     }
1695
1696
1697     // ---------------------------------------------------- Context Inner Class
1698
1699
1700     protected static final class MappedContext extends MapElement<Void> {
1701         public volatile ContextVersion[] versions;
1702
1703         public MappedContext(String name, ContextVersion firstVersion) {
1704             super(name, null);
1705             this.versions = new ContextVersion[] { firstVersion };
1706         }
1707     }
1708
1709     protected static final class ContextVersion extends MapElement<Context> {
1710         public final String path;
1711         public final int slashCount;
1712         public final WebResourceRoot resources;
1713         public String[] welcomeResources;
1714         public MappedWrapper defaultWrapper = null;
1715         public MappedWrapper[] exactWrappers = new MappedWrapper[0];
1716         public MappedWrapper[] wildcardWrappers = new MappedWrapper[0];
1717         public MappedWrapper[] extensionWrappers = new MappedWrapper[0];
1718         public int nesting = 0;
1719         private volatile boolean paused;
1720
1721         public ContextVersion(String version, String path, int slashCount,
1722                 Context context, WebResourceRoot resources,
1723                 String[] welcomeResources) {
1724             super(version, context);
1725             this.path = path;
1726             this.slashCount = slashCount;
1727             this.resources = resources;
1728             this.welcomeResources = welcomeResources;
1729         }
1730
1731         public boolean isPaused() {
1732             return paused;
1733         }
1734
1735         public void markPaused() {
1736             paused = true;
1737         }
1738     }
1739
1740     // ---------------------------------------------------- Wrapper Inner Class
1741
1742
1743     protected static class MappedWrapper extends MapElement<Wrapper> {
1744
1745         public final boolean jspWildCard;
1746         public final boolean resourceOnly;
1747
1748         public MappedWrapper(String name, Wrapper wrapper, boolean jspWildCard,
1749                 boolean resourceOnly) {
1750             super(name, wrapper);
1751             this.jspWildCard = jspWildCard;
1752             this.resourceOnly = resourceOnly;
1753         }
1754     }
1755 }
1756