Author: markt Date: Wed Oct 31 22:06:26 2012 New Revision: 1404380 URL: http://svn.apache.org/viewvc?rev=1404380&view=rev Log: Fix https://issues.apache.org/bugzilla/show_bug.cgi?id=54068 Re-write the fragment ordering algorithm to over come multiple problems. Expand the unit tests to cover the identified issues.
Modified: tomcat/tc7.0.x/trunk/ (props changed) tomcat/tc7.0.x/trunk/java/org/apache/catalina/deploy/WebXml.java tomcat/tc7.0.x/trunk/test/org/apache/catalina/deploy/TestWebXmlOrdering.java tomcat/tc7.0.x/trunk/webapps/docs/changelog.xml Propchange: tomcat/tc7.0.x/trunk/ ------------------------------------------------------------------------------ Merged /tomcat/trunk:r1404374 Modified: tomcat/tc7.0.x/trunk/java/org/apache/catalina/deploy/WebXml.java URL: http://svn.apache.org/viewvc/tomcat/tc7.0.x/trunk/java/org/apache/catalina/deploy/WebXml.java?rev=1404380&r1=1404379&r2=1404380&view=diff ============================================================================== --- tomcat/tc7.0.x/trunk/java/org/apache/catalina/deploy/WebXml.java (original) +++ tomcat/tc7.0.x/trunk/java/org/apache/catalina/deploy/WebXml.java Wed Oct 31 22:06:26 2012 @@ -5,9 +5,9 @@ * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at - * + * * http://www.apache.org/licenses/LICENSE-2.0 - * + * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. @@ -26,7 +26,6 @@ import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.LinkedHashSet; -import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Map.Entry; @@ -53,10 +52,10 @@ import org.apache.tomcat.util.res.String * StandardContext will check validity of values (eg URL formats etc) */ public class WebXml { - + protected static final String ORDER_OTHERS = "org.apache.catalina.order.others"; - + private static final StringManager sm = StringManager.getManager(Constants.Package); @@ -107,7 +106,7 @@ public class WebXml { after.add(ORDER_OTHERS); } public Set<String> getAfterOrdering() { return after; } - + private Set<String> before = new LinkedHashSet<String>(); public void addBeforeOrdering(String fragmentName) { before.add(fragmentName); @@ -122,7 +121,7 @@ public class WebXml { public Set<String> getBeforeOrdering() { return before; } // Common elements and attributes - + // Required attribute of web-app element public String getVersion() { StringBuilder sb = new StringBuilder(3); @@ -137,7 +136,7 @@ public class WebXml { */ public void setVersion(String version) { if (version == null) return; - + // Update major and minor version // Expected format is n.n - allow for any number of digits just in case String major = null; @@ -161,7 +160,7 @@ public class WebXml { majorVersion = 0; } } - + if (minor == null || minor.length() == 0) { minorVersion = 0; } else { @@ -218,13 +217,13 @@ public class WebXml { log.warn(sm.getString("webxml.unrecognisedPublicId", publicId)); } } - + // Optional metadata-complete attribute private boolean metadataComplete = false; public boolean isMetadataComplete() { return metadataComplete; } public void setMetadataComplete(boolean metadataComplete) { this.metadataComplete = metadataComplete; } - + // Optional name element private String name = null; public String getName() { return name; } @@ -243,7 +242,7 @@ public class WebXml { private int minorVersion = 0; public int getMajorVersion() { return majorVersion; } public int getMinorVersion() { return minorVersion; } - + // web-app elements // TODO: Ignored elements: // - description @@ -255,14 +254,14 @@ public class WebXml { public void setDisplayName(String displayName) { this.displayName = displayName; } - + // distributable private boolean distributable = false; public boolean isDistributable() { return distributable; } public void setDistributable(boolean distributable) { this.distributable = distributable; } - + // context-param // TODO: description (multiple with language) is ignored private Map<String,String> contextParams = new HashMap<String,String>(); @@ -270,7 +269,7 @@ public class WebXml { contextParams.put(param, value); } public Map<String,String> getContextParams() { return contextParams; } - + // filter // TODO: Should support multiple description elements with language // TODO: Should support multiple display-name elements with language @@ -288,7 +287,7 @@ public class WebXml { filters.put(filter.getFilterName(), filter); } public Map<String,FilterDef> getFilters() { return filters; } - + // filter-mapping private Set<FilterMap> filterMaps = new LinkedHashSet<FilterMap>(); private Set<String> filterMappingNames = new HashSet<String>(); @@ -297,7 +296,7 @@ public class WebXml { filterMappingNames.add(filterMap.getFilterName()); } public Set<FilterMap> getFilterMappings() { return filterMaps; } - + // listener // TODO: description (multiple with language) is ignored // TODO: display-name (multiple with language) is ignored @@ -307,7 +306,7 @@ public class WebXml { listeners.add(className); } public Set<String> getListeners() { return listeners; } - + // servlet // TODO: description (multiple with language) is ignored // TODO: display-name (multiple with language) is ignored @@ -322,7 +321,7 @@ public class WebXml { } } public Map<String,ServletDef> getServlets() { return servlets; } - + // servlet-mapping private Map<String,String> servletMappings = new HashMap<String,String>(); private Set<String> servletMappingNames = new HashSet<String>(); @@ -331,7 +330,7 @@ public class WebXml { servletMappingNames.add(servletName); } public Map<String,String> getServletMappings() { return servletMappings; } - + // session-config // Digester will check there is only one of these private SessionConfig sessionConfig = new SessionConfig(); @@ -339,14 +338,14 @@ public class WebXml { this.sessionConfig = sessionConfig; } public SessionConfig getSessionConfig() { return sessionConfig; } - + // mime-mapping private Map<String,String> mimeMappings = new HashMap<String,String>(); public void addMimeMapping(String extension, String mimeType) { mimeMappings.put(extension, mimeType); } public Map<String,String> getMimeMappings() { return mimeMappings; } - + // welcome-file-list merge control private boolean replaceWelcomeFiles = false; private boolean alwaysAddWelcomeFiles = true; @@ -375,14 +374,14 @@ public class WebXml { welcomeFiles.add(welcomeFile); } public Set<String> getWelcomeFiles() { return welcomeFiles; } - + // error-page private Map<String,ErrorPage> errorPages = new HashMap<String,ErrorPage>(); public void addErrorPage(ErrorPage errorPage) { errorPages.put(errorPage.getName(), errorPage); } public Map<String,ErrorPage> getErrorPages() { return errorPages; } - + // Digester will check there is only one jsp-config // jsp-config/taglib or taglib (2.3 and earlier) private Map<String,String> taglibs = new HashMap<String,String>(); @@ -395,7 +394,7 @@ public class WebXml { taglibs.put(uri, location); } public Map<String,String> getTaglibs() { return taglibs; } - + // jsp-config/jsp-property-group private Set<JspPropertyGroup> jspPropertyGroups = new LinkedHashSet<JspPropertyGroup>(); @@ -417,7 +416,7 @@ public class WebXml { public Set<SecurityConstraint> getSecurityConstraints() { return securityConstraints; } - + // login-config // Digester will check there is only one of these private LoginConfig loginConfig = null; @@ -425,7 +424,7 @@ public class WebXml { this.loginConfig = loginConfig; } public LoginConfig getLoginConfig() { return loginConfig; } - + // security-role // TODO: description (multiple with language) is ignored private Set<String> securityRoles = new HashSet<String>(); @@ -433,7 +432,7 @@ public class WebXml { securityRoles.add(securityRole); } public Set<String> getSecurityRoles() { return securityRoles; } - + // env-entry // TODO: Should support multiple description elements with language private Map<String,ContextEnvironment> envEntries = @@ -448,7 +447,7 @@ public class WebXml { envEntries.put(envEntry.getName(),envEntry); } public Map<String,ContextEnvironment> getEnvEntries() { return envEntries; } - + // ejb-ref // TODO: Should support multiple description elements with language private Map<String,ContextEjb> ejbRefs = new HashMap<String,ContextEjb>(); @@ -456,7 +455,7 @@ public class WebXml { ejbRefs.put(ejbRef.getName(),ejbRef); } public Map<String,ContextEjb> getEjbRefs() { return ejbRefs; } - + // ejb-local-ref // TODO: Should support multiple description elements with language private Map<String,ContextLocalEjb> ejbLocalRefs = @@ -467,7 +466,7 @@ public class WebXml { public Map<String,ContextLocalEjb> getEjbLocalRefs() { return ejbLocalRefs; } - + // service-ref // TODO: Should support multiple description elements with language // TODO: Should support multiple display-names elements with language @@ -478,7 +477,7 @@ public class WebXml { serviceRefs.put(serviceRef.getName(), serviceRef); } public Map<String,ContextService> getServiceRefs() { return serviceRefs; } - + // resource-ref // TODO: Should support multiple description elements with language private Map<String,ContextResource> resourceRefs = @@ -495,7 +494,7 @@ public class WebXml { public Map<String,ContextResource> getResourceRefs() { return resourceRefs; } - + // resource-env-ref // TODO: Should support multiple description elements with language private Map<String,ContextResourceEnvRef> resourceEnvRefs = @@ -512,7 +511,7 @@ public class WebXml { public Map<String,ContextResourceEnvRef> getResourceEnvRefs() { return resourceEnvRefs; } - + // message-destination-ref // TODO: Should support multiple description elements with language private Map<String,MessageDestinationRef> messageDestinationRefs = @@ -533,7 +532,7 @@ public class WebXml { public Map<String,MessageDestinationRef> getMessageDestinationRefs() { return messageDestinationRefs; } - + // message-destination // TODO: Should support multiple description elements with language // TODO: Should support multiple display-names elements with language @@ -556,7 +555,7 @@ public class WebXml { public Map<String,MessageDestination> getMessageDestinations() { return messageDestinations; } - + // locale-encoding-mapping-list private Map<String,String> localeEncodingMappings = new HashMap<String,String>(); @@ -566,10 +565,10 @@ public class WebXml { public Map<String,String> getLocalEncodingMappings() { return localeEncodingMappings; } - + // Attributes not defined in web.xml or web-fragment.xml - + // URL of JAR / exploded JAR for this web-fragment private URL uRL = null; public void setURL(URL url) { this.uRL = url; } @@ -585,26 +584,26 @@ public class WebXml { buf.append(getURL()); return buf.toString(); } - + private static final String INDENT2 = " "; private static final String INDENT4 = " "; private static final String INDENT6 = " "; - + /** * Generate a web.xml in String form that matches the representation stored * in this object. - * + * * @return The complete contents of web.xml as a String */ public String toXml() { StringBuilder sb = new StringBuilder(2048); - + // TODO - Various, icon, description etc elements are skipped - mainly // because they are ignored when web.xml is parsed - see above // Declaration sb.append("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"); - + // Root element sb.append("<web-app xmlns=\"http://java.sun.com/xml/ns/javaee\"\n"); sb.append(" xmlns:xsi="); @@ -618,11 +617,11 @@ public class WebXml { sb.append(" metadata-complete=\"true\">\n\n"); appendElement(sb, INDENT2, "display-name", displayName); - + if (isDistributable()) { sb.append(" <distributable/>\n\n"); } - + for (Map.Entry<String, String> entry : contextParams.entrySet()) { sb.append(" <context-param>\n"); appendElement(sb, INDENT4, "param-name", entry.getKey()); @@ -630,7 +629,7 @@ public class WebXml { sb.append(" </context-param>\n"); } sb.append('\n'); - + for (Map.Entry<String, FilterDef> entry : filters.entrySet()) { FilterDef filterDef = entry.getValue(); sb.append(" <filter>\n"); @@ -745,7 +744,7 @@ public class WebXml { sb.append(" </servlet-mapping>\n"); } sb.append('\n'); - + if (sessionConfig != null) { sb.append(" <session-config>\n"); appendElement(sb, INDENT4, "session-timeout", @@ -770,7 +769,7 @@ public class WebXml { } sb.append(" </session-config>\n\n"); } - + for (Map.Entry<String, String> entry : mimeMappings.entrySet()) { sb.append(" <mime-mapping>\n"); appendElement(sb, INDENT4, "extension", entry.getKey()); @@ -778,7 +777,7 @@ public class WebXml { sb.append(" </mime-mapping>\n"); } sb.append('\n'); - + if (welcomeFiles.size() > 0) { sb.append(" <welcome-file-list>\n"); for (String welcomeFile : welcomeFiles) { @@ -786,7 +785,7 @@ public class WebXml { } sb.append(" </welcome-file-list>\n\n"); } - + for (ErrorPage errorPage : errorPages.values()) { sb.append(" <error-page>\n"); if (errorPage.getExceptionType() == null) { @@ -839,7 +838,7 @@ public class WebXml { } sb.append(" </jsp-config>\n\n"); } - + for (SecurityConstraint constraint : securityConstraints) { sb.append(" <security-constraint>\n"); appendElement(sb, INDENT4, "display-name", @@ -895,13 +894,13 @@ public class WebXml { } sb.append(" </login-config>\n\n"); } - + for (String roleName : securityRoles) { sb.append(" <security-role>\n"); appendElement(sb, INDENT4, "role-name", roleName); sb.append(" </security-role>\n"); } - + for (ContextEnvironment envEntry : envEntries.values()) { sb.append(" <env-entry>\n"); appendElement(sb, INDENT4, "description", @@ -967,7 +966,7 @@ public class WebXml { sb.append(" </ejb-local-ref>\n"); } sb.append('\n'); - + for (ContextService serviceRef : serviceRefs.values()) { sb.append(" <service-ref>\n"); appendElement(sb, INDENT4, "description", @@ -1023,7 +1022,7 @@ public class WebXml { sb.append(" </service-ref>\n"); } sb.append('\n'); - + for (ContextResource resourceRef : resourceRefs.values()) { sb.append(" <resource-ref>\n"); appendElement(sb, INDENT4, "description", @@ -1170,7 +1169,7 @@ public class WebXml { /** * Configure a {@link Context} using the stored web.xml representation. - * + * * @param context The context to be configured */ public void configureContext(Context context) { @@ -1182,7 +1181,7 @@ public class WebXml { // Everything else in order context.setEffectiveMajorVersion(getMajorVersion()); context.setEffectiveMinorVersion(getMinorVersion()); - + for (Entry<String, String> entry : contextParams.entrySet()) { context.addParameter(entry.getKey(), entry.getValue()); } @@ -1231,7 +1230,7 @@ public class WebXml { } // messageDestinations were ignored in Tomcat 6, so ignore here - + context.setIgnoreAnnotations(metadataComplete); for (Entry<String, String> entry : mimeMappings.entrySet()) { context.addMimeMapping(entry.getKey(), entry.getValue()); @@ -1257,7 +1256,7 @@ public class WebXml { // Description is ignored // Display name is ignored // Icons are ignored - + // jsp-file gets passed to the JSP Servlet as an init-param if (servlet.getLoadOnStartup() != null) { @@ -1267,7 +1266,7 @@ public class WebXml { wrapper.setEnabled(servlet.getEnabled().booleanValue()); } wrapper.setName(servlet.getServletName()); - Map<String,String> params = servlet.getParameterMap(); + Map<String,String> params = servlet.getParameterMap(); for (Entry<String, String> entry : params.entrySet()) { wrapper.addInitParameter(entry.getKey(), entry.getValue()); } @@ -1334,13 +1333,13 @@ public class WebXml { entry.getValue(), entry.getKey()); context.getJspConfigDescriptor().getTaglibs().add(descriptor); } - + // Context doesn't use version directly - + for (String welcomeFile : welcomeFiles) { /* * The following will result in a welcome file of "" so don't add - * that to the context + * that to the context * <welcome-file-list> * <welcome-file/> * </welcome-file-list> @@ -1370,10 +1369,10 @@ public class WebXml { } } } - + /** * Merge the supplied web fragments into this main web.xml. - * + * * @param fragments The fragments to merge in * @return <code>true</code> if merge is successful, else * <code>false</code> @@ -1381,7 +1380,7 @@ public class WebXml { public boolean merge(Set<WebXml> fragments) { // As far as possible, process in alphabetical order so it is easy to // check everything is present - + // Merge rules vary from element to element. See SRV.8.2.3 WebXml temp = new WebXml(); @@ -1396,7 +1395,7 @@ public class WebXml { if (displayName == null) { for (WebXml fragment : fragments) { - String value = fragment.getDisplayName(); + String value = fragment.getDisplayName(); if (value != null) { if (temp.getDisplayName() == null) { temp.setDisplayName(value); @@ -1484,7 +1483,7 @@ public class WebXml { entry.getKey(), fragment.getName(), fragment.getURL())); - + return false; } } else { @@ -1616,7 +1615,7 @@ public class WebXml { } } } - + // Add fragment mappings for (Map.Entry<String,String> mapping : servletMappingsToAdd) { addServletMapping(mapping.getKey(), mapping.getValue()); @@ -1637,7 +1636,7 @@ public class WebXml { entry.getKey(), fragment.getName(), fragment.getURL())); - + return false; } } else { @@ -1647,7 +1646,7 @@ public class WebXml { } } servlets.putAll(temp.getServlets()); - + if (sessionConfig.getSessionTimeout() == null) { for (WebXml fragment : fragments) { Integer value = fragment.getSessionConfig().getSessionTimeout(); @@ -1671,7 +1670,7 @@ public class WebXml { temp.getSessionConfig().getSessionTimeout().toString()); } } - + if (sessionConfig.getCookieName() == null) { for (WebXml fragment : fragments) { String value = fragment.getSessionConfig().getCookieName(); @@ -1848,7 +1847,7 @@ public class WebXml { sessionConfig.getSessionTrackingModes().addAll( temp.getSessionConfig().getSessionTrackingModes()); } - + for (WebXml fragment : fragments) { if (!mergeMap(fragment.getTaglibs(), taglibs, temp.getTaglibs(), fragment, "Taglibs")) { @@ -1867,7 +1866,7 @@ public class WebXml { return true; } - + private static <T extends ResourceBase> boolean mergeResourceMap( Map<String, T> fragmentResources, Map<String, T> mainResources, Map<String, T> tempResources, WebXml fragment) { @@ -1890,12 +1889,12 @@ public class WebXml { } } else { tempResources.put(resourceName, resource); - } + } } } return true; } - + private static <T> boolean mergeMap(Map<String,T> fragmentMap, Map<String,T> mainMap, Map<String,T> tempMap, WebXml fragment, String mapName) { @@ -1922,7 +1921,7 @@ public class WebXml { } return true; } - + private static boolean mergeFilter(FilterDef src, FilterDef dest, boolean failOnConflict) { if (dest.getAsyncSupported() == null) { @@ -1942,7 +1941,7 @@ public class WebXml { return false; } } - + for (Map.Entry<String,String> srcEntry : src.getParameterMap().entrySet()) { if (dest.getParameterMap().containsKey(srcEntry.getKey())) { @@ -1956,7 +1955,7 @@ public class WebXml { } return true; } - + private static boolean mergeServlet(ServletDef src, ServletDef dest, boolean failOnConflict) { // These tests should be unnecessary... @@ -1966,8 +1965,8 @@ public class WebXml { if (src.getServletClass() != null && src.getJspFile() != null) { return false; } - - + + if (dest.getServletClass() == null && dest.getJspFile() == null) { dest.setServletClass(src.getServletClass()); dest.setJspFile(src.getJspFile()); @@ -1983,12 +1982,12 @@ public class WebXml { return false; } } - + // Additive for (SecurityRoleRef securityRoleRef : src.getSecurityRoleRefs()) { dest.addSecurityRoleRef(securityRoleRef); } - + if (dest.getLoadOnStartup() == null) { if (src.getLoadOnStartup() != null) { dest.setLoadOnStartup(src.getLoadOnStartup().toString()); @@ -1999,7 +1998,7 @@ public class WebXml { return false; } } - + if (dest.getEnabled() == null) { if (src.getEnabled() != null) { dest.setEnabled(src.getEnabled().toString()); @@ -2010,7 +2009,7 @@ public class WebXml { return false; } } - + for (Map.Entry<String,String> srcEntry : src.getParameterMap().entrySet()) { if (dest.getParameterMap().containsKey(srcEntry.getKey())) { @@ -2022,14 +2021,14 @@ public class WebXml { dest.addInitParameter(srcEntry.getKey(), srcEntry.getValue()); } } - + if (dest.getMultipartDef() == null) { dest.setMultipartDef(src.getMultipartDef()); } else if (src.getMultipartDef() != null) { return mergeMultipartDef(src.getMultipartDef(), dest.getMultipartDef(), failOnConflict); } - + if (dest.getAsyncSupported() == null) { if (src.getAsyncSupported() != null) { dest.setAsyncSupported(src.getAsyncSupported().toString()); @@ -2040,7 +2039,7 @@ public class WebXml { return false; } } - + return true; } @@ -2087,13 +2086,13 @@ public class WebXml { return true; } - - + + /** * Generates the sub-set of the web-fragment.xml files to be processed in * the order that the fragments must be processed as per the rules in the * Servlet spec. - * + * * @param application The application web.xml file * @param fragments The map of fragment names to web fragments * @return Ordered list of web-fragment.xml files to process @@ -2102,14 +2101,14 @@ public class WebXml { Map<String,WebXml> fragments) { Set<WebXml> orderedFragments = new LinkedHashSet<WebXml>(); - + boolean absoluteOrdering = (application.getAbsoluteOrdering() != null); - + if (absoluteOrdering) { // Only those fragments listed should be processed Set<String> requestedOrder = application.getAbsoluteOrdering(); - + for (String requestedName : requestedOrder) { if (WebXml.ORDER_OTHERS.equals(requestedName)) { // Add all fragments not named explicitly at this point @@ -2131,75 +2130,137 @@ public class WebXml { } } } else { - List<String> order = new LinkedList<String>(); - // Start by adding all fragments - order doesn't matter - order.addAll(fragments.keySet()); - - // Now go through and move elements to start/end depending on if - // they specify others - for (WebXml fragment : fragments.values()) { - String name = fragment.getName(); - if (fragment.getBeforeOrdering().contains(WebXml.ORDER_OTHERS)) { - // Move to beginning - order.remove(name); - order.add(0, name); - } else if (fragment.getAfterOrdering().contains(WebXml.ORDER_OTHERS)) { - // Move to end - order.remove(name); - order.add(name); - } - } - - // Now apply remaining ordering + // Stage 1. Make all dependencies bi-directional - this makes the + // next stage simpler. for (WebXml fragment : fragments.values()) { - String name = fragment.getName(); for (String before : fragment.getBeforeOrdering()) { - if (!before.equals(WebXml.ORDER_OTHERS) && - order.contains(before) && - order.indexOf(before) < order.indexOf(name)) { - order.remove(name); - order.add(order.indexOf(before), name); + if (!before.equals(ORDER_OTHERS)) { + fragments.get(before).addAfterOrdering(fragment.getName()); } } for (String after : fragment.getAfterOrdering()) { - if (!after.equals(WebXml.ORDER_OTHERS) && - order.contains(after) && - order.indexOf(after) > order.indexOf(name)) { - order.remove(name); - order.add(order.indexOf(after) + 1, name); + if (!after.equals(ORDER_OTHERS)) { + fragments.get(after).addBeforeOrdering(fragment.getName()); } } } - - // Finally check ordering was applied correctly - if there are - // errors then that indicates circular references + + // Stage 2. Make all fragments that are implicitly before/after + // others explicitly so. This is iterative so the next + // stage doesn't have to be. for (WebXml fragment : fragments.values()) { - String name = fragment.getName(); - for (String before : fragment.getBeforeOrdering()) { - if (!before.equals(WebXml.ORDER_OTHERS) && - order.contains(before) && - order.indexOf(before) < order.indexOf(name)) { - throw new IllegalArgumentException( - sm.getString("webXml.mergeConflictOrder")); - } + if (fragment.getBeforeOrdering().contains(ORDER_OTHERS)) { + makeBeforeOthersExplicit(fragment.getAfterOrdering(), fragments); } - for (String after : fragment.getAfterOrdering()) { - if (!after.equals(WebXml.ORDER_OTHERS) && - order.contains(after) && - order.indexOf(after) > order.indexOf(name)) { - throw new IllegalArgumentException( - sm.getString("webXml.mergeConflictOrder")); - } + if (fragment.getAfterOrdering().contains(ORDER_OTHERS)) { + makeAfterOthersExplicit(fragment.getBeforeOrdering(), fragments); } } - - // Build the ordered list - for (String name : order) { - orderedFragments.add(fragments.get(name)); + + // Stage 3. Separate into three groups + Set<WebXml> beforeSet = new HashSet<WebXml>(); + Set<WebXml> othersSet = new HashSet<WebXml>(); + Set<WebXml> afterSet = new HashSet<WebXml>(); + + for (WebXml fragment : fragments.values()) { + if (fragment.getBeforeOrdering().contains(ORDER_OTHERS)) { + beforeSet.add(fragment); + fragment.getBeforeOrdering().remove(ORDER_OTHERS); + } else if (fragment.getAfterOrdering().contains(ORDER_OTHERS)) { + afterSet.add(fragment); + fragment.getAfterOrdering().remove(ORDER_OTHERS); + } else { + othersSet.add(fragment); + } } + + // Stage 4. Decouple the groups so the ordering requirements for + // each fragment in the group only refer to other fragments + // in the group. Ordering requirements outside the group + // will be handled by processing the groups in order. + // Note: Only after ordering requirements are considered. + // This is OK because of the processing in stage 1. + decoupleOtherGroups(beforeSet); + decoupleOtherGroups(othersSet); + decoupleOtherGroups(afterSet); + + // Stage 5. Order each group + // Note: Only after ordering requirements are considered. + // This is OK because of the processing in stage 1. + orderFragments(orderedFragments, beforeSet); + orderFragments(orderedFragments, othersSet); + orderFragments(orderedFragments, afterSet); } - + return orderedFragments; } -} + private static void decoupleOtherGroups(Set<WebXml> group) { + Set<String> names = new HashSet<String>(); + for (WebXml fragment : group) { + names.add(fragment.getName()); + } + for (WebXml fragment : group) { + Iterator<String> after = fragment.getAfterOrdering().iterator(); + while (after.hasNext()) { + String entry = after.next(); + if (!names.contains(entry)) { + after.remove(); + } + } + } + } + private static void orderFragments(Set<WebXml> orderedFragments, + Set<WebXml> unordered) { + Set<WebXml> addedThisRound = new HashSet<WebXml>(); + Set<WebXml> addedLastRound = new HashSet<WebXml>(); + while (unordered.size() > 0) { + Iterator<WebXml> source = unordered.iterator(); + while (source.hasNext()) { + WebXml fragment = source.next(); + for (WebXml toRemove : addedLastRound) { + fragment.getAfterOrdering().remove(toRemove.getName()); + } + if (fragment.getAfterOrdering().isEmpty()) { + addedThisRound.add(fragment); + orderedFragments.add(fragment); + source.remove(); + } + } + if (addedThisRound.size() == 0) { + // Circular + throw new IllegalArgumentException( + sm.getString("webXml.mergeConflictOrder")); + } + addedLastRound.clear(); + addedLastRound.addAll(addedThisRound); + addedThisRound.clear(); + } + } + + private static void makeBeforeOthersExplicit(Set<String> beforeOrdering, + Map<String, WebXml> fragments) { + for (String before : beforeOrdering) { + if (!before.equals(ORDER_OTHERS)) { + WebXml webXml = fragments.get(before); + if (!webXml.getBeforeOrdering().contains(ORDER_OTHERS)) { + webXml.addBeforeOrderingOthers(); + makeBeforeOthersExplicit(webXml.getAfterOrdering(), fragments); + } + } + } + } + + private static void makeAfterOthersExplicit(Set<String> afterOrdering, + Map<String, WebXml> fragments) { + for (String after : afterOrdering) { + if (!after.equals(ORDER_OTHERS)) { + WebXml webXml = fragments.get(after); + if (!webXml.getAfterOrdering().contains(ORDER_OTHERS)) { + webXml.addAfterOrderingOthers(); + makeAfterOthersExplicit(webXml.getBeforeOrdering(), fragments); + } + } + } + } +} Modified: tomcat/tc7.0.x/trunk/test/org/apache/catalina/deploy/TestWebXmlOrdering.java URL: http://svn.apache.org/viewvc/tomcat/tc7.0.x/trunk/test/org/apache/catalina/deploy/TestWebXmlOrdering.java?rev=1404380&r1=1404379&r2=1404380&view=diff ============================================================================== --- tomcat/tc7.0.x/trunk/test/org/apache/catalina/deploy/TestWebXmlOrdering.java (original) +++ tomcat/tc7.0.x/trunk/test/org/apache/catalina/deploy/TestWebXmlOrdering.java Wed Oct 31 22:06:26 2012 @@ -17,9 +17,11 @@ package org.apache.catalina.deploy; -import java.util.HashMap; +import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; +import java.util.LinkedHashMap; +import java.util.List; import java.util.Map; import java.util.Set; @@ -42,9 +44,15 @@ public class TestWebXmlOrdering { private WebXml e; private WebXml f; private Map<String,WebXml> fragments; + private int posA; + private int posB; + private int posC; + private int posD; + private int posE; + private int posF; @Before - public void setUp() throws Exception { + public void setUp() { app = new WebXml(); a = new WebXml(); a.setName("a"); @@ -58,7 +66,8 @@ public class TestWebXmlOrdering { e.setName("e"); f = new WebXml(); f.setName("f"); - fragments = new HashMap<String,WebXml>(); + // Control the input order + fragments = new LinkedHashMap<String,WebXml>(); fragments.put("a",a); fragments.put("b",b); fragments.put("c",c); @@ -185,83 +194,483 @@ public class TestWebXmlOrdering { assertFalse(iter.hasNext()); } + private void doRelativeOrderingTest(RelativeOrderingTestRunner runner) { + // Confirm we have all 720 possible input orders + // Set<String> orders = new HashSet<>(); + + // Test all possible input orders since some bugs were discovered that + // depended on input order + for (int i = 0; i < 6; i++) { + for (int j = 0; j < 5; j++) { + for (int k = 0; k < 4; k++) { + for (int l = 0; l < 3; l++) { + for (int m = 0; m < 2; m++) { + setUp(); + runner.init(); + ArrayList<WebXml> source = new ArrayList<WebXml>(); + source.addAll(fragments.values()); + Map<String,WebXml> input = + new LinkedHashMap<String,WebXml>(); + + WebXml one = source.remove(i); + input.put(one.getName(), one); + + WebXml two = source.remove(j); + input.put(two.getName(), two); + + WebXml three = source.remove(k); + input.put(three.getName(), three); + + WebXml four = source.remove(l); + input.put(four.getName(), four); + + WebXml five = source.remove(m); + input.put(five.getName(), five); + + WebXml six = source.remove(0); + input.put(six.getName(), six); + + /* + String order = one.getName() + two.getName() + + three.getName() + four.getName() + + five.getName() + six.getName(); + orders.add(order); + */ + + Set<WebXml> ordered = + WebXml.orderWebFragments(app, input); + populatePositions(ordered); + + runner.validate(getOrder(ordered)); + } + } + } + } + } + // System.out.println(orders.size()); + } + + private String getOrder(Set<WebXml> ordered) { + StringBuilder sb = new StringBuilder(ordered.size()); + for (WebXml webXml : ordered) { + sb.append(webXml.getName()); + } + return sb.toString(); + } + + private void populatePositions(Set<WebXml> ordered) { + List<WebXml> indexed = new ArrayList<WebXml>(); + indexed.addAll(ordered); + + posA = indexed.indexOf(a); + posB = indexed.indexOf(b); + posC = indexed.indexOf(c); + posD = indexed.indexOf(d); + posE = indexed.indexOf(e); + posF = indexed.indexOf(f); + } + @Test public void testOrderWebFragmentsRelative1() { // First example from servlet spec - a.addAfterOrderingOthers(); - a.addAfterOrdering("c"); - b.addBeforeOrderingOthers(); - c.addAfterOrderingOthers(); - f.addBeforeOrderingOthers(); - f.addBeforeOrdering("b"); - - Set<WebXml> ordered = WebXml.orderWebFragments(app, fragments); - - Iterator<WebXml> iter = ordered.iterator(); - assertEquals(f,iter.next()); - assertEquals(b,iter.next()); - assertEquals(d,iter.next()); - assertEquals(e,iter.next()); - assertEquals(c,iter.next()); - assertEquals(a,iter.next()); + doRelativeOrderingTest(new RelativeTestRunner1()); } @Test public void testOrderWebFragmentsRelative2() { // Second example - use fragment a for no-id fragment - a.addAfterOrderingOthers(); - a.addBeforeOrdering("c"); - b.addBeforeOrderingOthers(); - d.addAfterOrderingOthers(); - e.addBeforeOrderingOthers(); + doRelativeOrderingTest(new RelativeTestRunner2()); + } - Set<WebXml> ordered = WebXml.orderWebFragments(app, fragments); + @Test + public void testOrderWebFragmentsRelative3() { + // Third example from spec with e & f added + doRelativeOrderingTest(new RelativeTestRunner3()); + } - Iterator<WebXml> iter = ordered.iterator(); - // A number of orders are possible but the algorithm is deterministic - // and this order is valid. If this fails after a change to the - // algorithm, then check to see if the new order is also valid. - assertEquals(b,iter.next()); - assertEquals(e,iter.next()); - assertEquals(f,iter.next()); - assertEquals(a,iter.next()); - assertEquals(c,iter.next()); - assertEquals(d,iter.next()); + @Test + public void testOrderWebFragmentsRelative4Bug54068() { + // Simple sequence that failed for some inputs + doRelativeOrderingTest(new RelativeTestRunner4()); } @Test - public void testOrderWebFragmentsRelative3() { - // Third example from spec - a.addAfterOrdering("b"); - c.addBeforeOrderingOthers(); - fragments.remove("e"); - fragments.remove("f"); + public void testOrderWebFragmentsRelative5Bug54068() { + // Simple sequence that failed for some inputs + doRelativeOrderingTest(new RelativeTestRunner5()); + } - Set<WebXml> ordered = WebXml.orderWebFragments(app, fragments); + @Test + public void testOrderWebFragmentsRelative6Bug54068() { + // Simple sequence that failed for some inputs + doRelativeOrderingTest(new RelativeTestRunner6()); + } - Iterator<WebXml> iter = ordered.iterator(); - // A number of orders are possible but the algorithm is deterministic - // and this order is valid. If this fails after a change to the - // algorithm, then check to see if the new order is also valid. - assertEquals(c,iter.next()); - assertEquals(d,iter.next()); - assertEquals(b,iter.next()); - assertEquals(a,iter.next()); + @Test + public void testOrderWebFragmentsRelative7() { + // Reference loop (but not circular dependencies) + doRelativeOrderingTest(new RelativeTestRunner7()); } @Test - public void testOrderWebFragmentsrelativeCircular() { + public void testOrderWebFragmentsRelative8() { + // More complex, trying to break the algorithm + doRelativeOrderingTest(new RelativeTestRunner8()); + } + + @Test + public void testOrderWebFragmentsRelative9() { + // Variation on bug 54068 + doRelativeOrderingTest(new RelativeTestRunner9()); + } + + @Test + public void testOrderWebFragmentsRelative10() { + // Variation on bug 54068 + doRelativeOrderingTest(new RelativeTestRunner10()); + } + + + @Test(expected=IllegalArgumentException.class) + public void testOrderWebFragmentsrelativeCircular1() { a.addBeforeOrdering("b"); b.addBeforeOrdering("a"); - Exception exception = null; + WebXml.orderWebFragments(app, fragments); + } + + @Test(expected=IllegalArgumentException.class) + public void testOrderWebFragmentsrelativeCircular2() { + a.addBeforeOrderingOthers(); + b.addAfterOrderingOthers(); + c.addBeforeOrdering("a"); + c.addAfterOrdering("b"); + + WebXml.orderWebFragments(app, fragments); + } + + private interface RelativeOrderingTestRunner { + void init(); + void validate(String order); + } + + private class RelativeTestRunner1 implements RelativeOrderingTestRunner { + + @Override + public void init() { + a.addAfterOrderingOthers(); + a.addAfterOrdering("c"); + b.addBeforeOrderingOthers(); + c.addAfterOrderingOthers(); + f.addBeforeOrderingOthers(); + f.addBeforeOrdering("b"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + //a.addAfterOrderingOthers(); + assertTrue(order, posA > posB); + assertTrue(order, posA > posC); + assertTrue(order, posA > posD); + assertTrue(order, posA > posE); + assertTrue(order, posA > posF); + + // a.addAfterOrdering("c"); + assertTrue(order, posA > posC); + + // b.addBeforeOrderingOthers(); + assertTrue(order, posB < posC); + + // c.addAfterOrderingOthers(); + assertTrue(order, posC > posB); + assertTrue(order, posC > posD); + assertTrue(order, posC > posE); + assertTrue(order, posC > posF); + + // f.addBeforeOrderingOthers(); + assertTrue(order, posF < posA); + assertTrue(order, posF < posB); + assertTrue(order, posF < posC); + assertTrue(order, posF < posD); + assertTrue(order, posF < posE); + + // f.addBeforeOrdering("b"); + assertTrue(order, posF < posB); + } + } + + private class RelativeTestRunner2 implements RelativeOrderingTestRunner { - try { - WebXml.orderWebFragments(app, fragments); - } catch (Exception e1) { - exception = e1; + @Override + public void init() { + a.addAfterOrderingOthers(); + a.addBeforeOrdering("c"); + b.addBeforeOrderingOthers(); + d.addAfterOrderingOthers(); + e.addBeforeOrderingOthers(); } - assertTrue(exception instanceof IllegalArgumentException); + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // a.addAfterOrderingOthers(); + assertTrue(order, posA > posB); + assertTrue(order, posA > posE); + assertTrue(order, posA > posF); + + // a.addBeforeOrdering("c"); + assertTrue(order, posC > posA); + assertTrue(order, posC > posB); + assertTrue(order, posC > posE); + assertTrue(order, posC > posF); + + // b.addBeforeOrderingOthers(); + assertTrue(order, posB < posA); + assertTrue(order, posB < posC); + assertTrue(order, posB < posD); + assertTrue(order, posB < posF); + + // d.addAfterOrderingOthers(); + assertTrue(order, posD > posB); + assertTrue(order, posD > posE); + assertTrue(order, posD > posF); + + // e.addBeforeOrderingOthers(); + assertTrue(order, posE < posA); + assertTrue(order, posE < posC); + assertTrue(order, posE < posD); + assertTrue(order, posE < posF); + } + } + + private class RelativeTestRunner3 implements RelativeOrderingTestRunner { + + @Override + public void init() { + a.addAfterOrdering("b"); + c.addBeforeOrderingOthers(); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // a.addAfterOrdering("b"); + assertTrue(order, posA > posB); + + // c.addBeforeOrderingOthers(); + assertTrue(order, posC < posA); + assertTrue(order, posC < posB); + assertTrue(order, posC < posD); + assertTrue(order, posC < posE); + assertTrue(order, posC < posF); + } + } + + private class RelativeTestRunner4 implements RelativeOrderingTestRunner { + + @Override + public void init() { + b.addAfterOrdering("a"); + c.addAfterOrdering("b"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // b.addAfterOrdering("a"); + assertTrue(order, posB > posA); + + // c.addAfterOrdering("b"); + assertTrue(order, posC > posB); + } + } + + private class RelativeTestRunner5 implements RelativeOrderingTestRunner { + + @Override + public void init() { + b.addBeforeOrdering("a"); + c.addBeforeOrdering("b"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // b.addBeforeOrdering("a"); + assertTrue(order, posB < posA); + + // c.addBeforeOrdering("b"); + assertTrue(order, posC < posB); + } + } + + private class RelativeTestRunner6 implements RelativeOrderingTestRunner { + + @Override + public void init() { + b.addBeforeOrdering("a"); + b.addAfterOrdering("c"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // b.addBeforeOrdering("a"); + assertTrue(order, posB < posA); + + //b.addAfterOrdering("c"); + assertTrue(order, posB > posC); + } + } + + private class RelativeTestRunner7 implements RelativeOrderingTestRunner { + + @Override + public void init() { + b.addBeforeOrdering("a"); + c.addBeforeOrdering("b"); + a.addAfterOrdering("c"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // b.addBeforeOrdering("a"); + assertTrue(order, posB < posA); + + // c.addBeforeOrdering("b"); + assertTrue(order, posC < posB); + + // a.addAfterOrdering("c"); + assertTrue(order, posA > posC); + } + } + + private class RelativeTestRunner8 implements RelativeOrderingTestRunner { + + @Override + public void init() { + a.addBeforeOrderingOthers(); + a.addBeforeOrdering("b"); + b.addBeforeOrderingOthers(); + c.addAfterOrdering("b"); + d.addAfterOrdering("c"); + e.addAfterOrderingOthers(); + f.addAfterOrderingOthers(); + f.addAfterOrdering("e"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // a.addBeforeOrderingOthers(); + assertTrue(order, posA < posB); + assertTrue(order, posA < posC); + assertTrue(order, posA < posD); + assertTrue(order, posA < posE); + assertTrue(order, posA < posF); + + // a.addBeforeOrdering("b"); + assertTrue(order, posA < posB); + + // b.addBeforeOrderingOthers(); + assertTrue(order, posB < posC); + assertTrue(order, posB < posD); + assertTrue(order, posB < posE); + assertTrue(order, posB < posF); + + // c.addAfterOrdering("b"); + assertTrue(order, posC > posB); + + // d.addAfterOrdering("c"); + assertTrue(order, posD > posC); + + // e.addAfterOrderingOthers(); + assertTrue(order, posE > posA); + assertTrue(order, posE > posB); + assertTrue(order, posE > posC); + assertTrue(order, posE > posD); + + // f.addAfterOrderingOthers(); + assertTrue(order, posF > posA); + assertTrue(order, posF > posB); + assertTrue(order, posF > posC); + assertTrue(order, posF > posD); + assertTrue(order, posF > posE); + + // f.addAfterOrdering("e"); + assertTrue(order, posF > posE); + } + } + + private class RelativeTestRunner9 implements RelativeOrderingTestRunner { + + @Override + public void init() { + a.addBeforeOrderingOthers(); + b.addBeforeOrdering("a"); + c.addBeforeOrdering("b"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // a.addBeforeOrderingOthers(); + assertTrue(order, posA < posD); + assertTrue(order, posA < posE); + assertTrue(order, posA < posF); + + // b.addBeforeOrdering("a"); + assertTrue(order, posB < posA); + + // c.addBeforeOrdering("b"); + assertTrue(order, posC < posB); + } + } + + private class RelativeTestRunner10 implements RelativeOrderingTestRunner { + + @Override + public void init() { + a.addAfterOrderingOthers(); + b.addAfterOrdering("a"); + c.addAfterOrdering("b"); + } + + @Override + public void validate(String order) { + // There is some duplication in the tests below - it is easier to + // check the tests are complete this way. + + // a.addAfterOrderingOthers(); + assertTrue(order, posA > posD); + assertTrue(order, posA > posE); + assertTrue(order, posA > posF); + + // b.addAfterOrdering("a"); + assertTrue(order, posB > posA); + + // c.addAfterOrdering("b"); + assertTrue(order, posC > posB); + } } } Modified: tomcat/tc7.0.x/trunk/webapps/docs/changelog.xml URL: http://svn.apache.org/viewvc/tomcat/tc7.0.x/trunk/webapps/docs/changelog.xml?rev=1404380&r1=1404379&r2=1404380&view=diff ============================================================================== --- tomcat/tc7.0.x/trunk/webapps/docs/changelog.xml (original) +++ tomcat/tc7.0.x/trunk/webapps/docs/changelog.xml Wed Oct 31 22:06:26 2012 @@ -81,6 +81,11 @@ <bug>54054</bug>: Do not share shell environment variables between multiple instances of the CGI servlet. (markt) </fix> + <fix> + <bug>54068</bug>: Rewrite the web fragment ordering algorithm to resolve + multiple issues that resulted in incorrect ordering or failure to find + a correct, valid order. (markt) + </fix> </changelog> </subsection> <subsection name="Coyote"> --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@tomcat.apache.org For additional commands, e-mail: dev-h...@tomcat.apache.org