View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.myfaces.config;
20  
21  import org.apache.myfaces.config.element.ConfigOthersSlot;
22  import org.apache.myfaces.config.element.FacesConfig;
23  import org.apache.myfaces.config.element.FacesConfigData;
24  import org.apache.myfaces.config.element.FacesConfigNameSlot;
25  import org.apache.myfaces.config.element.OrderSlot;
26  import org.apache.myfaces.config.element.Ordering;
27  import org.apache.myfaces.config.impl.digester.DigesterFacesConfigDispenserImpl;
28  import org.apache.myfaces.config.util.CyclicDependencyException;
29  import org.apache.myfaces.config.util.DirectedAcyclicGraphVerifier;
30  import org.apache.myfaces.config.util.Vertex;
31  import org.apache.myfaces.spi.FacesConfigurationMerger;
32  import org.apache.myfaces.spi.FacesConfigurationProvider;
33  import org.apache.myfaces.spi.FacesConfigurationProviderFactory;
34  
35  import javax.faces.FacesException;
36  import javax.faces.context.ExternalContext;
37  import java.util.ArrayList;
38  import java.util.Collections;
39  import java.util.Comparator;
40  import java.util.Iterator;
41  import java.util.LinkedList;
42  import java.util.List;
43  import java.util.logging.Level;
44  import java.util.logging.Logger;
45  
46  /**
47   * Default impl of the FacesConfigurationMerger-SPI.
48   *
49   * This impl gets all FacesConfig data from the current FacesConfigurationProvider SPI impl and merges
50   * it into one FacesConfigData object using the ordering and sorting rules of the JSF spec.
51   *
52   * @author Jakob Korherr
53   */
54  public class DefaultFacesConfigurationMerger extends FacesConfigurationMerger
55  {
56  
57      private static final Logger log = Logger.getLogger(DefaultFacesConfigurationMerger.class.getName());
58  
59      @Override
60      public FacesConfigData getFacesConfigData(ExternalContext externalContext)
61      {
62          // get the FacesConfigProvider SPI impl in order to get the faces-config data for the merging process
63          FacesConfigurationProvider facesConfigProvider = FacesConfigurationProviderFactory
64                  .getFacesConfigurationProviderFactory(externalContext).getFacesConfigurationProvider(externalContext);
65  
66          FacesConfigDispenser dispenser = new DigesterFacesConfigDispenserImpl();
67  
68          // standard-faces-config.xml
69          dispenser.feed(facesConfigProvider.getStandardFacesConfig(externalContext));
70  
71          // META-INF/services/[factory name] factory definitions
72          dispenser.feed(facesConfigProvider.getMetaInfServicesFacesConfig(externalContext));
73  
74          // WEB-INF/faces-config.xml
75          FacesConfig webAppFacesConfig = facesConfigProvider.getWebAppFacesConfig(externalContext);
76  
77          //read metadata-complete attribute on WEB-INF/faces-config.xml
78          boolean metadataComplete = false;
79          if(webAppFacesConfig != null)
80          {
81              metadataComplete = Boolean.valueOf(webAppFacesConfig.getMetadataComplete());
82          }
83          else
84          {
85              //assume false if no faces-config.xml was found
86              //metadata-complete can only be specified in faces-config.xml per the JSF 2.0 schema
87              metadataComplete = false;
88          }
89  
90          // faces-config data from Annotations
91          FacesConfig annotationFacesConfig = facesConfigProvider
92                  .getAnnotationsFacesConfig(externalContext, metadataComplete);
93          if (annotationFacesConfig != null)
94          {
95              dispenser.feed(annotationFacesConfig);
96          }
97  
98          List<FacesConfig> appConfigResources = new ArrayList<FacesConfig>();
99  
100         // META-INF/faces-config.xml files
101         appConfigResources.addAll(facesConfigProvider.getClassloaderFacesConfig(externalContext));
102         
103         // faces-config.xml files from javax.faces.CONFIG_FILES
104         appConfigResources.addAll(facesConfigProvider.getContextSpecifiedFacesConfig(externalContext));
105 
106 
107         // apply the ordering and sorting algorithm 
108         orderAndFeedArtifacts(dispenser, appConfigResources, webAppFacesConfig);
109 
110         LogMetaInfUtils.logMetaInf();
111 
112         return dispenser;
113     }
114 
115     protected void orderAndFeedArtifacts(FacesConfigDispenser dispenser,
116                                          List<FacesConfig> appConfigResources,
117                                          FacesConfig webAppConfig)
118         throws FacesException
119     {
120         if (webAppConfig != null && webAppConfig.getAbsoluteOrdering() != null)
121         {
122             if (webAppConfig.getOrdering() != null)
123             {
124                 if (log.isLoggable(Level.WARNING))
125                 {
126                     log.warning("<ordering> element found in application faces config. " +
127                             "This description will be ignored and the actions described " +
128                             "in <absolute-ordering> element will be taken into account instead.");
129                 }
130             }
131             //Absolute ordering
132 
133             //1. Scan all appConfigResources and create a list
134             //containing all resources not mentioned directly, preserving the
135             //order founded
136             List<FacesConfig> othersResources = new ArrayList<FacesConfig>();
137             List<OrderSlot> slots = webAppConfig.getAbsoluteOrdering().getOrderList();
138             for (FacesConfig resource : appConfigResources)
139             {
140                 // First condition: if faces-config.xml does not have name it is
141                 // 1) pre-JSF-2.0 or
142                 // 2) has no <name> element,
143                 // -> in both cases cannot be ordered
144                 // Second condition : faces-config.xml has a name but <ordering>
145                 // element does not have slot with that name
146                 //  -> resource can be ordered, but will fit into <others /> element
147                 if ((resource.getName() == null) ||
148                         (resource.getName() != null && !containsResourceInSlot(slots, resource.getName())))
149                 {
150                     othersResources.add(resource);
151                 }
152             }
153 
154             //2. Scan slot by slot and merge information according
155             for (OrderSlot slot : webAppConfig.getAbsoluteOrdering().getOrderList())
156             {
157                 if (slot instanceof ConfigOthersSlot)
158                 {
159                     //Add all mentioned in othersResources
160                     for (FacesConfig resource : othersResources)
161                     {
162                         dispenser.feed(resource);
163                     }
164                 }
165                 else
166                 {
167                     //Add it to the sorted list
168                     FacesConfigNameSlot nameSlot = (FacesConfigNameSlot) slot;
169                     // We need to check if the resource is on appConfigResources, otherwise we can
170                     // ignore it safely.
171                     FacesConfig targetFacesConfig = getFacesConfig(appConfigResources, nameSlot.getName());
172                     if (targetFacesConfig != null)
173                     {
174                         dispenser.feed(targetFacesConfig);
175                     }
176                 }
177             }
178         }
179         else if (!appConfigResources.isEmpty())
180         {
181             //Relative ordering
182             for (FacesConfig resource : appConfigResources)
183             {
184                 if (resource.getAbsoluteOrdering() != null)
185                 {
186                     if (log.isLoggable(Level.WARNING))
187                     {
188                         log.warning("<absolute-ordering> element found in application " +
189                                 "configuration resource "+resource.getName()+". " +
190                                 "This description will be ignored and the actions described " +
191                                 "in <ordering> elements will be taken into account instead.");
192                     }
193                 }
194             }
195 
196             List<FacesConfig> postOrderedList = getPostOrderedList(appConfigResources);
197 
198             List<FacesConfig> sortedList = sortRelativeOrderingList(postOrderedList);
199 
200             if (sortedList == null)
201             {
202                 //The previous algorithm can't sort correctly, try this one
203                 sortedList = applySortingAlgorithm(appConfigResources);
204             }
205 
206             for (FacesConfig resource : sortedList)
207             {
208                 //Feed
209                 dispenser.feed(resource);
210             }
211         }
212 
213         //add null check for apps which don't have a faces-config.xml (e.g. tomahawk examples for 1.1/1.2)
214         if(webAppConfig != null)
215         {
216             dispenser.feed(webAppConfig);
217         }
218     }
219 
220     /**
221      * Sort using topological ordering algorithm.
222      *
223      * @param appConfigResources
224      * @return
225      * @throws FacesException
226      */
227     protected List<FacesConfig> applySortingAlgorithm(List<FacesConfig> appConfigResources) throws FacesException
228     {
229 
230         //0. Convert the references into a graph
231         List<Vertex<FacesConfig>> vertexList = new ArrayList<Vertex<FacesConfig>>();
232         for (FacesConfig config : appConfigResources)
233         {
234             Vertex<FacesConfig> v = null;
235             if (config.getName() != null)
236             {
237                 v = new Vertex<FacesConfig>(config.getName(), config);
238             }
239             else
240             {
241                 v = new Vertex<FacesConfig>(config);
242             }
243             vertexList.add(v);
244         }
245 
246         //1. Resolve dependencies (before-after rules) and mark referenced vertex
247         boolean[] referencedVertex = new boolean[vertexList.size()];
248 
249         for (int i = 0; i < vertexList.size(); i++)
250         {
251             Vertex<FacesConfig> v = vertexList.get(i);
252             FacesConfig f = (FacesConfig) v.getNode();
253 
254             if (f.getOrdering() != null)
255             {
256                 for (OrderSlot slot : f.getOrdering().getBeforeList())
257                 {
258                     if (slot instanceof FacesConfigNameSlot)
259                     {
260                         String name = ((FacesConfigNameSlot) slot).getName();
261                         int j = DirectedAcyclicGraphVerifier.findVertex(vertexList, name);
262                         Vertex<FacesConfig> v1 = vertexList.get(j);
263                         if (v1 != null)
264                         {
265                             referencedVertex[i] = true;
266                             referencedVertex[j] = true;
267                             v1.addDependency(v);
268                         }
269                     }
270                 }
271                 for (OrderSlot slot : f.getOrdering().getAfterList())
272                 {
273                     if (slot instanceof FacesConfigNameSlot)
274                     {
275                         String name = ((FacesConfigNameSlot) slot).getName();
276                         int j = DirectedAcyclicGraphVerifier.findVertex(vertexList, name);
277                         Vertex<FacesConfig> v1 = vertexList.get(j);
278                         if (v1 != null)
279                         {
280                             referencedVertex[i] = true;
281                             referencedVertex[j] = true;
282                             v.addDependency(v1);
283                         }
284                     }
285                 }
286             }
287         }
288 
289         //2. Classify into categories
290         List<Vertex<FacesConfig>> beforeAfterOthersList = new ArrayList<Vertex<FacesConfig>>();
291         List<Vertex<FacesConfig>> othersList = new ArrayList<Vertex<FacesConfig>>();
292         List<Vertex<FacesConfig>> referencedList = new ArrayList<Vertex<FacesConfig>>();
293 
294         for (int i = 0; i < vertexList.size(); i++)
295         {
296             if (!referencedVertex[i])
297             {
298                 Vertex<FacesConfig> v = vertexList.get(i);
299                 FacesConfig f = (FacesConfig) v.getNode();
300                 boolean added = false;
301                 if (f.getOrdering() != null)
302                 {
303                     if (!f.getOrdering().getBeforeList().isEmpty())
304                     {
305                         added = true;
306                         beforeAfterOthersList.add(v);
307                     }
308                     else if (!f.getOrdering().getAfterList().isEmpty())
309                     {
310                         added = true;
311                         beforeAfterOthersList.add(v);
312                     }
313                 }
314                 if (!added)
315                 {
316                     othersList.add(v);
317                 }
318             }
319             else
320             {
321                 referencedList.add(vertexList.get(i));
322             }
323         }
324 
325         //3. Sort all referenced nodes
326         try
327         {
328             DirectedAcyclicGraphVerifier.topologicalSort(referencedList);
329         }
330         catch (CyclicDependencyException e)
331         {
332             e.printStackTrace();
333         }
334 
335         //4. Add referenced nodes
336         List<FacesConfig> sortedList = new ArrayList<FacesConfig>();
337         for (Vertex<FacesConfig> v : referencedList)
338         {
339             sortedList.add((FacesConfig)v.getNode());
340         }
341 
342         //5. add nodes without instructions at the end
343         for (Vertex<FacesConfig> v : othersList)
344         {
345             sortedList.add((FacesConfig)v.getNode());
346         }
347 
348         //6. add before/after nodes
349         for (Vertex<FacesConfig> v : beforeAfterOthersList)
350         {
351             FacesConfig f = (FacesConfig) v.getNode();
352             boolean added = false;
353             if (f.getOrdering() != null)
354             {
355                 if (!f.getOrdering().getBeforeList().isEmpty())
356                 {
357                     added = true;
358                     sortedList.add(0,f);
359                 }
360             }
361             if (!added)
362             {
363                 sortedList.add(f);
364             }
365         }
366 
367         //Check
368         for (int i = 0; i < sortedList.size(); i++)
369         {
370             FacesConfig resource = sortedList.get(i);
371 
372             if (resource.getOrdering() != null)
373             {
374                 for (OrderSlot slot : resource.getOrdering().getBeforeList())
375                 {
376                     if (slot instanceof FacesConfigNameSlot)
377                     {
378                         String name = ((FacesConfigNameSlot) slot).getName();
379                         if (name != null && !"".equals(name))
380                         {
381                             boolean founded = false;
382                             for (int j = i-1; j >= 0; j--)
383                             {
384                                 if (name.equals(sortedList.get(j).getName()))
385                                 {
386                                     founded=true;
387                                     break;
388                                 }
389                             }
390                             if (founded)
391                             {
392                                 log.severe("Circular references detected when sorting " +
393                                           "application config resources. Use absolute ordering instead.");
394                                 throw new FacesException("Circular references detected when sorting " +
395                                         "application config resources. Use absolute ordering instead.");
396                             }
397                         }
398                     }
399                 }
400                 for (OrderSlot slot : resource.getOrdering().getAfterList())
401                 {
402                     if (slot instanceof FacesConfigNameSlot)
403                     {
404                         String name = ((FacesConfigNameSlot) slot).getName();
405                         if (name != null && !"".equals(name))
406                         {
407                             boolean founded = false;
408                             for (int j = i+1; j < sortedList.size(); j++)
409                             {
410                                 if (name.equals(sortedList.get(j).getName()))
411                                 {
412                                     founded=true;
413                                     break;
414                                 }
415                             }
416                             if (founded)
417                             {
418                                 log.severe("Circular references detected when sorting " +
419                                     "application config resources. Use absolute ordering instead.");
420                                 throw new FacesException("Circular references detected when sorting " +
421                                     "application config resources. Use absolute ordering instead.");
422                             }
423                         }
424                     }
425                 }
426             }
427         }
428 
429         return sortedList;
430     }
431 
432     /**
433      * Sort a list of pre ordered elements. It scans one by one the elements
434      * and apply the conditions mentioned by Ordering object if it is available.
435      *
436      * The preOrderedList ensures that application config resources referenced by
437      * other resources are processed first, making more easier the sort procedure.
438      *
439      * @param preOrderedList
440      * @return
441      */
442     protected List<FacesConfig> sortRelativeOrderingList(List<FacesConfig> preOrderedList)
443     {
444         List<FacesConfig> sortedList = new ArrayList<FacesConfig>();
445 
446         for (int i=0; i < preOrderedList.size(); i++)
447         {
448             FacesConfig resource = preOrderedList.get(i);
449             if (resource.getOrdering() != null)
450             {
451                 if (resource.getOrdering().getBeforeList().isEmpty() &&
452                     resource.getOrdering().getAfterList().isEmpty())
453                 {
454                     //No order rules, just put it as is
455                     sortedList.add(resource);
456                 }
457                 else if (resource.getOrdering().getBeforeList().isEmpty())
458                 {
459                     //Only after rules
460                     applyAfterRule(sortedList, resource);
461                 }
462                 else if (resource.getOrdering().getAfterList().isEmpty())
463                 {
464                     //Only before rules
465 
466                     //Resolve if there is a later reference to this node before
467                     //apply it
468                     boolean referenceNode = false;
469 
470                     for (int j = i+1; j < preOrderedList.size(); j++)
471                     {
472                         FacesConfig pointingResource = preOrderedList.get(j);
473                         for (OrderSlot slot : pointingResource.getOrdering().getBeforeList())
474                         {
475                             if (slot instanceof FacesConfigNameSlot &&
476                                     resource.getName().equals(((FacesConfigNameSlot)slot).getName()) )
477                             {
478                                 referenceNode = true;
479                             }
480                             if (slot instanceof ConfigOthersSlot)
481                             {
482                                 //No matter if there is a reference, because this rule
483                                 //is not strict and before other ordering is unpredictable.
484                                 //
485                                 referenceNode = false;
486                                 break;
487                             }
488                         }
489                         if (referenceNode)
490                         {
491                             break;
492                         }
493                         for (OrderSlot slot : pointingResource.getOrdering().getAfterList())
494                         {
495                             if (slot instanceof FacesConfigNameSlot &&
496                                 resource.getName().equals(((FacesConfigNameSlot)slot).getName()) )
497                             {
498                                 referenceNode = true;
499                                 break;
500                             }
501                         }
502                     }
503 
504                     applyBeforeRule(sortedList, resource, referenceNode);
505                 }
506                 else
507                 {
508                     //Both before and after rules
509                     //In this case we should compare before and after rules
510                     //and the one with names takes precedence over the other one.
511                     //It both have names references, before rules takes
512                     //precedence over after
513                     //after some action is applied a check of the condition is made.
514                     int beforeWeight = 0;
515                     int afterWeight = 0;
516                     for (OrderSlot slot : resource.getOrdering()
517                             .getBeforeList())
518                     {
519                         if (slot instanceof FacesConfigNameSlot)
520                         {
521                             beforeWeight++;
522                         }
523                     }
524                     for (OrderSlot slot : resource.getOrdering()
525                             .getAfterList())
526                     {
527                         if (slot instanceof FacesConfigNameSlot)
528                         {
529                             afterWeight++;
530                         }
531                     }
532 
533                     if (beforeWeight >= afterWeight)
534                     {
535                         applyBeforeRule(sortedList, resource,false);
536                     }
537                     else
538                     {
539                         applyAfterRule(sortedList, resource);
540                     }
541 
542 
543                 }
544             }
545             else
546             {
547                 //No order rules, just put it as is
548                 sortedList.add(resource);
549             }
550         }
551 
552         //Check
553         for (int i = 0; i < sortedList.size(); i++)
554         {
555             FacesConfig resource = sortedList.get(i);
556 
557             if (resource.getOrdering() != null)
558             {
559                 for (OrderSlot slot : resource.getOrdering().getBeforeList())
560                 {
561                     if (slot instanceof FacesConfigNameSlot)
562                     {
563                         String name = ((FacesConfigNameSlot) slot).getName();
564                         if (name != null && !"".equals(name))
565                         {
566                             boolean founded = false;
567                             for (int j = i-1; j >= 0; j--)
568                             {
569                                 if (name.equals(sortedList.get(j).getName()))
570                                 {
571                                     founded=true;
572                                     break;
573                                 }
574                             }
575                             if (founded)
576                             {
577                                 //Cyclic reference
578                                 return null;
579                             }
580                         }
581                     }
582                 }
583                 for (OrderSlot slot : resource.getOrdering().getAfterList())
584                 {
585                     if (slot instanceof FacesConfigNameSlot)
586                     {
587                         String name = ((FacesConfigNameSlot) slot).getName();
588                         if (name != null && !"".equals(name))
589                         {
590                             boolean founded = false;
591                             for (int j = i+1; j < sortedList.size(); j++)
592                             {
593                                 if (name.equals(sortedList.get(j).getName()))
594                                 {
595                                     founded=true;
596                                     break;
597                                 }
598                             }
599                             if (founded)
600                             {
601                                 //Cyclic reference
602                                 return null;
603                             }
604                         }
605                     }
606                 }
607             }
608         }
609 
610         return sortedList;
611     }
612 
613     private void applyBeforeRule(List<FacesConfig> sortedList, FacesConfig resource, boolean referenced)
614             throws FacesException
615     {
616         //Only before rules
617         boolean configOthers = false;
618         List<String> names = new ArrayList<String>();
619 
620         for (OrderSlot slot : resource.getOrdering().getBeforeList())
621         {
622             if (slot instanceof ConfigOthersSlot)
623             {
624                 configOthers = true;
625                 break;
626             }
627             else
628             {
629                 FacesConfigNameSlot nameSlot = (FacesConfigNameSlot) slot;
630                 names.add(nameSlot.getName());
631             }
632         }
633 
634         if (configOthers)
635         {
636             //<before>....<others/></before> case
637             //other reference where already considered when
638             //pre ordered list was calculated, so just add to the end.
639 
640             //There is one very special case, and it is when there
641             //is another resource with a reference on it. In this case,
642             //it is better do not apply this rule and add it to the end
643             //to give the chance to the other one to be applied.
644             if (resource.getOrdering().getBeforeList().size() > 1)
645             {
646                 //If there is a reference apply it
647                 sortedList.add(0,resource);
648             }
649             else if (!referenced)
650             {
651                 //If it is not referenced apply it
652                 sortedList.add(0,resource);
653             }
654             else
655             {
656                 //if it is referenced bypass the rule and add it to the end
657                 sortedList.add(resource);
658             }
659         }
660         else
661         {
662             //Scan the nearest reference and add it after
663             boolean founded = false;
664             for (int i = 0; i < sortedList.size() ; i++)
665             {
666                 if (names.contains(sortedList.get(i).getName()))
667                 {
668                     sortedList.add(i,resource);
669                     founded = true;
670                     break;
671                 }
672             }
673             if (!founded)
674             {
675                 //just add it to the end
676                 sortedList.add(resource);
677             }
678         }
679     }
680 
681     private void applyAfterRule(List<FacesConfig> sortedList, FacesConfig resource) throws FacesException
682     {
683         boolean configOthers = false;
684         List<String> names = new ArrayList<String>();
685 
686         for (OrderSlot slot : resource.getOrdering().getAfterList())
687         {
688             if (slot instanceof ConfigOthersSlot)
689             {
690                 configOthers = true;
691                 break;
692             }
693             else
694             {
695                 FacesConfigNameSlot nameSlot = (FacesConfigNameSlot) slot;
696                 names.add(nameSlot.getName());
697             }
698         }
699 
700         if (configOthers)
701         {
702             //<after>....<others/></after> case
703             //other reference where already considered when
704             //pre ordered list was calculated, so just add to the end.
705             sortedList.add(resource);
706         }
707         else
708         {
709             //Scan the nearest reference and add it after
710             boolean founded = false;
711             for (int i = sortedList.size()-1 ; i >=0 ; i--)
712             {
713                 if (names.contains(sortedList.get(i).getName()))
714                 {
715                     if (i+1 < sortedList.size())
716                     {
717                         sortedList.add(i+1,resource);
718                     }
719                     else
720                     {
721                         sortedList.add(resource);
722                     }
723                     founded = true;
724                     break;
725                 }
726             }
727             if (!founded)
728             {
729                 //just add it to the end
730                 sortedList.add(resource);
731             }
732         }
733     }
734 
735 
736     /**
737      * Pre Sort the appConfigResources, detecting cyclic references, so when sort process
738      * start, it is just necessary to traverse the preOrderedList once. To do that, we just
739      * scan "before" and "after" lists for references, and then those references are traversed
740      * again, so the first elements of the pre ordered list does not have references and
741      * the next elements has references to the already added ones.
742      *
743      * The elements on the preOrderedList looks like this:
744      *
745      * [ no ordering elements , referenced elements ... more referenced elements,
746      *  before others / after others non referenced elements]
747      *
748      * @param appConfigResources
749      * @return
750      */
751     protected List<FacesConfig> getPostOrderedList(final List<FacesConfig> appConfigResources) throws FacesException
752     {
753 
754         //0. Clean up: remove all not found resource references from the ordering
755         //descriptions.
756         List<String> availableReferences = new ArrayList<String>();
757         for (FacesConfig resource : appConfigResources)
758         {
759             String name = resource.getName();
760             if (name != null && !"".equals(name))
761             {
762                 availableReferences.add(name);
763             }
764         }
765 
766         for (FacesConfig resource : appConfigResources)
767         {
768             Ordering ordering = resource.getOrdering();
769             if (ordering != null)
770             {
771                 for (Iterator<OrderSlot> it =  resource.getOrdering().getBeforeList().iterator();it.hasNext();)
772                 {
773                     OrderSlot slot = it.next();
774                     if (slot instanceof FacesConfigNameSlot)
775                     {
776                         String name = ((FacesConfigNameSlot) slot).getName();
777                         if (!availableReferences.contains(name))
778                         {
779                             it.remove();
780                         }
781                     }
782                 }
783                 for (Iterator<OrderSlot> it =  resource.getOrdering().getAfterList().iterator();it.hasNext();)
784                 {
785                     OrderSlot slot = it.next();
786                     if (slot instanceof FacesConfigNameSlot)
787                     {
788                         String name = ((FacesConfigNameSlot) slot).getName();
789                         if (!availableReferences.contains(name))
790                         {
791                             it.remove();
792                         }
793                     }
794                 }
795             }
796         }
797 
798         List<FacesConfig> appFilteredConfigResources = null;
799 
800         //1. Pre filtering: Sort nodes according to its weight. The weight is the number of named
801         //nodes containing in both before and after lists. The sort is done from the more complex
802         //to the most simple
803         if (appConfigResources instanceof ArrayList)
804         {
805             appFilteredConfigResources = (List<FacesConfig>)
806                 ((ArrayList<FacesConfig>)appConfigResources).clone();
807         }
808         else
809         {
810             appFilteredConfigResources = new ArrayList<FacesConfig>();
811             appFilteredConfigResources.addAll(appConfigResources);
812         }
813         Collections.sort(appFilteredConfigResources,
814                 new Comparator<FacesConfig>()
815                 {
816                     public int compare(FacesConfig o1, FacesConfig o2)
817                     {
818                         int o1Weight = 0;
819                         int o2Weight = 0;
820                         if (o1.getOrdering() != null)
821                         {
822                             for (OrderSlot slot : o1.getOrdering()
823                                     .getBeforeList())
824                             {
825                                 if (slot instanceof FacesConfigNameSlot)
826                                 {
827                                     o1Weight++;
828                                 }
829                             }
830                             for (OrderSlot slot : o1.getOrdering()
831                                     .getAfterList())
832                             {
833                                 if (slot instanceof FacesConfigNameSlot)
834                                 {
835                                     o1Weight++;
836                                 }
837                             }
838                         }
839                         if (o2.getOrdering() != null)
840                         {
841                             for (OrderSlot slot : o2.getOrdering()
842                                     .getBeforeList())
843                             {
844                                 if (slot instanceof FacesConfigNameSlot)
845                                 {
846                                     o2Weight++;
847                                 }
848                             }
849                             for (OrderSlot slot : o2.getOrdering()
850                                     .getAfterList())
851                             {
852                                 if (slot instanceof FacesConfigNameSlot)
853                                 {
854                                     o2Weight++;
855                                 }
856                             }
857                         }
858                         return o2Weight - o1Weight;
859                     }
860                 });
861 
862         List<FacesConfig> postOrderedList = new LinkedList<FacesConfig>();
863         List<FacesConfig> othersList = new ArrayList<FacesConfig>();
864 
865         List<String> nameBeforeStack = new ArrayList<String>();
866         List<String> nameAfterStack = new ArrayList<String>();
867 
868         boolean[] visitedSlots = new boolean[appFilteredConfigResources.size()];
869 
870         //2. Scan and resolve conflicts
871         for (int i = 0; i < appFilteredConfigResources.size(); i++)
872         {
873             if (!visitedSlots[i])
874             {
875                 resolveConflicts(appFilteredConfigResources, i, visitedSlots,
876                         nameBeforeStack, nameAfterStack, postOrderedList, othersList, false);
877             }
878         }
879 
880         //Add othersList to postOrderedList so <before><others/></before> and <after><others/></after>
881         //ordering conditions are handled at last if there are not referenced by anyone
882         postOrderedList.addAll(othersList);
883 
884         return postOrderedList;
885     }
886 
887     private void resolveConflicts(final List<FacesConfig> appConfigResources, int index, boolean[] visitedSlots,
888             List<String> nameBeforeStack, List<String> nameAfterStack, List<FacesConfig> postOrderedList,
889             List<FacesConfig> othersList, boolean indexReferenced) throws FacesException
890     {
891         FacesConfig facesConfig = appConfigResources.get(index);
892 
893         if (nameBeforeStack.contains(facesConfig.getName()))
894         {
895             //Already referenced, just return. Later if there exists a
896             //circular reference, it will be detected and solved.
897             return;
898         }
899 
900         if (nameAfterStack.contains(facesConfig.getName()))
901         {
902             //Already referenced, just return. Later if there exists a
903             //circular reference, it will be detected and solved.
904             return;
905         }
906 
907         if (facesConfig.getOrdering() != null)
908         {
909             boolean pointingResource = false;
910 
911             //Deal with before restrictions first
912             for (OrderSlot slot : facesConfig.getOrdering().getBeforeList())
913             {
914                 if (slot instanceof FacesConfigNameSlot)
915                 {
916                     FacesConfigNameSlot nameSlot = (FacesConfigNameSlot) slot;
917                     //The resource pointed is not added yet?
918                     boolean alreadyAdded = false;
919                     for (FacesConfig res : postOrderedList)
920                     {
921                         if (nameSlot.getName().equals(res.getName()))
922                         {
923                             alreadyAdded = true;
924                             break;
925                         }
926                     }
927                     if (!alreadyAdded)
928                     {
929                         int indexSlot = -1;
930                         //Find it
931                         for (int i = 0; i < appConfigResources.size(); i++)
932                         {
933                             FacesConfig resource = appConfigResources.get(i);
934                             if (resource.getName() != null && nameSlot.getName().equals(resource.getName()))
935                             {
936                                 indexSlot = i;
937                                 break;
938                             }
939                         }
940 
941                         //Resource founded on appConfigResources
942                         if (indexSlot != -1)
943                         {
944                             pointingResource = true;
945                             //Add to nameStac
946                             nameBeforeStack.add(facesConfig.getName());
947 
948                             resolveConflicts(appConfigResources, indexSlot, visitedSlots,
949                                     nameBeforeStack, nameAfterStack, postOrderedList,
950                                     othersList,true);
951 
952                             nameBeforeStack.remove(facesConfig.getName());
953                         }
954                     }
955                     else
956                     {
957                         pointingResource = true;
958                     }
959                 }
960             }
961 
962             for (OrderSlot slot : facesConfig.getOrdering().getAfterList())
963             {
964                 if (slot instanceof FacesConfigNameSlot)
965                 {
966                     FacesConfigNameSlot nameSlot = (FacesConfigNameSlot) slot;
967                     //The resource pointed is not added yet?
968                     boolean alreadyAdded = false;
969                     for (FacesConfig res : postOrderedList)
970                     {
971                         if (nameSlot.getName().equals(res.getName()))
972                         {
973                             alreadyAdded = true;
974                             break;
975                         }
976                     }
977                     if (!alreadyAdded)
978                     {
979                         int indexSlot = -1;
980                         //Find it
981                         for (int i = 0; i < appConfigResources.size(); i++)
982                         {
983                             FacesConfig resource = appConfigResources.get(i);
984                             if (resource.getName() != null && nameSlot.getName().equals(resource.getName()))
985                             {
986                                 indexSlot = i;
987                                 break;
988                             }
989                         }
990 
991                         //Resource founded on appConfigResources
992                         if (indexSlot != -1)
993                         {
994                             pointingResource = true;
995                             //Add to nameStac
996                             nameAfterStack.add(facesConfig.getName());
997 
998                             resolveConflicts(appConfigResources, indexSlot, visitedSlots,
999                                     nameBeforeStack, nameAfterStack, postOrderedList,
1000                                     othersList,true);
1001 
1002                             nameAfterStack.remove(facesConfig.getName());
1003                         }
1004                     }
1005                     else
1006                     {
1007                         pointingResource = true;
1008                     }
1009                 }
1010             }
1011 
1012             if (facesConfig.getOrdering().getBeforeList().isEmpty() &&
1013                 facesConfig.getOrdering().getAfterList().isEmpty())
1014             {
1015                 //Fits in the category "others", put at beginning
1016                 postOrderedList.add(0,appConfigResources.get(index));
1017             }
1018             else if (pointingResource || indexReferenced)
1019             {
1020                 //If the node points to other or is referenced from other,
1021                 //add to the postOrderedList at the end
1022                 postOrderedList.add(appConfigResources.get(index));
1023             }
1024             else
1025             {
1026                 //Add to othersList
1027                 othersList.add(appConfigResources.get(index));
1028             }
1029         }
1030         else
1031         {
1032             //Add at start of the list, since does not have any ordering
1033             //instructions and on the next step makes than "before others" and "after others"
1034             //works correctly
1035             postOrderedList.add(0,appConfigResources.get(index));
1036         }
1037         //Set the node as visited
1038         visitedSlots[index] = true;
1039     }
1040 
1041     private FacesConfig getFacesConfig(List<FacesConfig> appConfigResources, String name)
1042     {
1043         for (FacesConfig cfg: appConfigResources)
1044         {
1045             if (cfg.getName() != null && name.equals(cfg.getName()))
1046             {
1047                 return cfg;
1048             }
1049         }
1050         return null;
1051     }
1052 
1053     private boolean containsResourceInSlot(List<OrderSlot> slots, String name)
1054     {
1055         for (OrderSlot slot: slots)
1056         {
1057             if (slot instanceof FacesConfigNameSlot)
1058             {
1059                 FacesConfigNameSlot nameSlot = (FacesConfigNameSlot) slot;
1060                 if (name.equals(nameSlot.getName()))
1061                 {
1062                     return true;
1063                 }
1064             }
1065         }
1066         return false;
1067     }
1068 
1069 }