1 // ========================================================================
2 // Copyright (c) 2009 Mort Bay Consulting Pty. Ltd.
3 // ------------------------------------------------------------------------
4 // All rights reserved. This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v1.0
6 // and Apache License v2.0 which accompanies this distribution.
7 // The Eclipse Public License is available at
8 // http://www.eclipse.org/legal/epl-v10.html
9 // The Apache License v2.0 is available at
10 // http://www.opensource.org/licenses/apache2.0.php
11 // You may elect to redistribute this code under either of these licenses.
12 // ========================================================================
13 package org.eclipse.jetty.webapp;
14
15 import java.util.ArrayList;
16 import java.util.HashMap;
17 import java.util.Iterator;
18 import java.util.LinkedList;
19 import java.util.List;
20 import java.util.Map;
21
22 import org.eclipse.jetty.util.resource.Resource;
23
24
25 /**
26 * Ordering
27 *
28 * Ordering options for jars in WEB-INF lib.
29 */
30 public interface Ordering
31 {
32
33 public List<Resource> order(List<Resource> fragments);
34 public boolean isAbsolute ();
35 public boolean hasOther();
36
37
38 /**
39 * AbsoluteOrdering
40 *
41 * An <absolute-order> element in web.xml
42 */
43 public static class AbsoluteOrdering implements Ordering
44 {
45 public static final String OTHER = "@@-OTHER-@@";
46 protected List<String> _order = new ArrayList<String>();
47 protected boolean _hasOther = false;
48 protected MetaData _metaData;
49
50 public AbsoluteOrdering (MetaData metaData)
51 {
52 _metaData = metaData;
53 }
54
55 /**
56 * Order the list of jars in WEB-INF/lib according to the ordering declarations in the descriptors
57 * @see org.eclipse.jetty.webapp.Ordering#order(java.util.List)
58 */
59 public List<Resource> order(List<Resource> jars)
60 {
61 List<Resource> orderedList = new ArrayList<Resource>();
62 List<Resource> tmp = new ArrayList<Resource>(jars);
63
64 //1. put everything into the list of named others, and take the named ones out of there,
65 //assuming we will want to use the <other> clause
66 Map<String,FragmentDescriptor> others = new HashMap<String,FragmentDescriptor>(_metaData.getNamedFragments());
67
68 //2. for each name, take out of the list of others, add to tail of list
69 int index = -1;
70 for (String item:_order)
71 {
72 if (!item.equals(OTHER))
73 {
74 FragmentDescriptor f = others.remove(item);
75 if (f != null)
76 {
77 Resource jar = _metaData.getJarForFragment(item);
78 orderedList.add(jar); //take from others and put into final list in order, ignoring duplicate names
79 //remove resource from list for resource matching name of descriptor
80 tmp.remove(jar);
81 }
82 }
83 else
84 index = orderedList.size(); //remember the index at which we want to add in all the others
85 }
86
87 //3. if <other> was specified, insert rest of the fragments
88 if (_hasOther)
89 {
90 orderedList.addAll((index < 0? 0: index), tmp);
91 }
92
93 return orderedList;
94 }
95
96
97 public boolean isAbsolute()
98 {
99 return true;
100 }
101
102 public void add (String name)
103 {
104 _order.add(name);
105 }
106
107 public void addOthers ()
108 {
109 if (_hasOther)
110 throw new IllegalStateException ("Duplicate <other> element in absolute ordering");
111
112 _hasOther = true;
113 _order.add(OTHER);
114 }
115
116
117 public boolean hasOther ()
118 {
119 return _hasOther;
120 }
121 }
122 /**
123 * RelativeOrdering
124 *
125 * A set of <order> elements in web-fragment.xmls.
126 */
127 public static class RelativeOrdering implements Ordering
128 {
129 protected MetaData _metaData;
130 protected LinkedList<Resource> _beforeOthers = new LinkedList<Resource>();
131 protected LinkedList<Resource> _afterOthers = new LinkedList<Resource>();
132 protected LinkedList<Resource> _noOthers = new LinkedList<Resource>();
133
134 public RelativeOrdering (MetaData metaData)
135 {
136 _metaData = metaData;
137 }
138 /**
139 * Order the list of jars according to the ordering declared
140 * in the various web-fragment.xml files.
141 * @see org.eclipse.jetty.webapp.Ordering#order(java.util.List)
142 */
143
144 public List<Resource> order(List<Resource> jars)
145 {
146 //for each jar, put it into the ordering according to the fragment ordering
147 for (Resource jar:jars)
148 {
149 //check if the jar has a fragment descriptor
150 FragmentDescriptor descriptor = _metaData.getFragment(jar);
151 if (descriptor != null)
152 {
153 switch (descriptor.getOtherType())
154 {
155 case None:
156 {
157 ((RelativeOrdering)_metaData.getOrdering()).addNoOthers(jar);
158 break;
159 }
160 case Before:
161 {
162 ((RelativeOrdering)_metaData.getOrdering()).addBeforeOthers(jar);
163 break;
164 }
165 case After:
166 {
167 ((RelativeOrdering)_metaData.getOrdering()).addAfterOthers(jar);
168 break;
169 }
170 }
171 }
172 else
173 {
174 //jar fragment has no descriptor, but there is a relative ordering in place, so it must be part of the others
175 ((RelativeOrdering)_metaData.getOrdering()).addNoOthers(jar);
176 }
177 }
178
179 //now apply the ordering
180 List<Resource> orderedList = new ArrayList<Resource>();
181 int maxIterations = 2;
182 boolean done = false;
183 do
184 {
185 //1. order the before-others according to any explicit before/after relationships
186 boolean changesBefore = orderList(_beforeOthers);
187
188 //2. order the after-others according to any explicit before/after relationships
189 boolean changesAfter = orderList(_afterOthers);
190
191 //3. order the no-others according to their explicit before/after relationships
192 boolean changesNone = orderList(_noOthers);
193
194 //we're finished on a clean pass through with no ordering changes
195 done = (!changesBefore && !changesAfter && !changesNone);
196 }
197 while (!done && (--maxIterations >0));
198
199 //4. merge before-others + no-others +after-others
200 if (!done)
201 throw new IllegalStateException("Circular references for fragments");
202
203 for (Resource r: _beforeOthers)
204 orderedList.add(r);
205 for (Resource r: _noOthers)
206 orderedList.add(r);
207 for(Resource r: _afterOthers)
208 orderedList.add(r);
209
210 return orderedList;
211 }
212
213
214 public boolean isAbsolute ()
215 {
216 return false;
217 }
218
219
220 public boolean hasOther ()
221 {
222 return !_beforeOthers.isEmpty() || !_afterOthers.isEmpty();
223 }
224
225 public void addBeforeOthers (Resource r)
226 {
227 _beforeOthers.addLast(r);
228 }
229
230 public void addAfterOthers (Resource r)
231 {
232 _afterOthers.addLast(r);
233 }
234
235 public void addNoOthers (Resource r)
236 {
237 _noOthers.addLast(r);
238 }
239
240 protected boolean orderList (LinkedList<Resource> list)
241 {
242 //Take a copy of the list so we can iterate over it and at the same time do random insertions
243 boolean changes = false;
244 List<Resource> iterable = new ArrayList<Resource>(list);
245 Iterator<Resource> itor = iterable.iterator();
246
247 while (itor.hasNext())
248 {
249 Resource r = itor.next();
250 FragmentDescriptor f = _metaData.getFragment(r);
251 if (f == null)
252 {
253 //no fragment for this resource so cannot have any ordering directives
254 continue;
255 }
256
257 //Handle any explicit <before> relationships for the fragment we're considering
258 List<String> befores = f.getBefores();
259 if (befores != null && !befores.isEmpty())
260 {
261 for (String b: befores)
262 {
263 //Fragment we're considering must be before b
264 //Check that we are already before it, if not, move us so that we are.
265 //If the name does not exist in our list, then get it out of the no-other list
266 if (!isBefore(list, f.getName(), b))
267 {
268 //b is not already before name, move it so that it is
269 int idx1 = getIndexOf(list, f.getName());
270 int idx2 = getIndexOf(list, b);
271
272 //if b is not in the same list
273 if (idx2 < 0)
274 {
275 changes = true;
276 // must be in the noOthers list or it would have been an error
277 Resource bResource = _metaData.getJarForFragment(b);
278 if (bResource != null)
279 {
280 //If its in the no-others list, insert into this list so that we are before it
281 if (_noOthers.remove(bResource))
282 {
283 insert(list, idx1+1, b);
284
285 }
286 }
287 }
288 else
289 {
290 //b is in the same list but b is before name, so swap it around
291 list.remove(idx1);
292 insert(list, idx2, f.getName());
293 changes = true;
294 }
295 }
296 }
297 }
298
299 //Handle any explicit <after> relationships
300 List<String> afters = f.getAfters();
301 if (afters != null && !afters.isEmpty())
302 {
303 for (String a: afters)
304 {
305 //Check that fragment we're considering is after a, moving it if possible if its not
306 if (!isAfter(list, f.getName(), a))
307 {
308 //name is not after a, move it
309 int idx1 = getIndexOf(list, f.getName());
310 int idx2 = getIndexOf(list, a);
311
312 //if a is not in the same list as name
313 if (idx2 < 0)
314 {
315 changes = true;
316 //take it out of the noOthers list and put it in the right place in this list
317 Resource aResource = _metaData.getJarForFragment(a);
318 if (aResource != null)
319 {
320 if (_noOthers.remove(aResource))
321 {
322 insert(list,idx1, aResource);
323 }
324 }
325 }
326 else
327 {
328 //a is in the same list as name, but in the wrong place, so move it
329 list.remove(idx2);
330 insert(list,idx1, a);
331 changes = true;
332 }
333 }
334 //Name we're considering must be after this name
335 //Check we're already after it, if not, move us so that we are.
336 //If the name does not exist in our list, then get it out of the no-other list
337 }
338 }
339 }
340
341 return changes;
342 }
343
344 /**
345 * Is fragment with name a before fragment with name b?
346 * @param list
347 * @param fragNameA
348 * @param fragNameB
349 * @return true if frament name A is before fragment name B
350 */
351 protected boolean isBefore (List<Resource> list, String fragNameA, String fragNameB)
352 {
353 //check if a and b are already in the same list, and b is already
354 //before a
355 int idxa = getIndexOf(list, fragNameA);
356 int idxb = getIndexOf(list, fragNameB);
357
358
359 if (idxb >=0 && idxb < idxa)
360 {
361 //a and b are in the same list but a is not before b
362 return false;
363 }
364
365 if (idxb < 0)
366 {
367 //a and b are not in the same list, but it is still possible that a is before
368 //b, depending on which list we're examining
369 if (list == _beforeOthers)
370 {
371 //The list we're looking at is the beforeOthers.If b is in the _afterOthers or the _noOthers, then by
372 //definition a is before it
373 return true;
374 }
375 else if (list == _afterOthers)
376 {
377 //The list we're looking at is the afterOthers, then a will be the tail of
378 //the final list. If b is in the beforeOthers list, then b will be before a and an error.
379 if (_beforeOthers.contains(fragNameB))
380 throw new IllegalStateException("Incorrect relationship: "+fragNameA+" before "+fragNameB);
381 else
382 return false; //b could be moved to the list
383 }
384 }
385
386 //a and b are in the same list and a is already before b
387 return true;
388 }
389
390
391 /**
392 * Is fragment name "a" after fragment name "b"?
393 * @param list
394 * @param fragNameA
395 * @param fragNameB
396 * @return true if fragment name A is after fragment name B
397 */
398 protected boolean isAfter(List<Resource> list, String fragNameA, String fragNameB)
399 {
400 int idxa = getIndexOf(list, fragNameA);
401 int idxb = getIndexOf(list, fragNameB);
402
403 if (idxb >=0 && idxa < idxb)
404 {
405 //a and b are both in the same list, but a is before b
406 return false;
407 }
408
409 if (idxb < 0)
410 {
411 //a and b are in different lists. a could still be after b depending on which list it is in.
412
413 if (list == _afterOthers)
414 {
415 //The list we're looking at is the afterOthers. If b is in the beforeOthers or noOthers then
416 //by definition a is after b because a is in the afterOthers list.
417 return true;
418 }
419 else if (list == _beforeOthers)
420 {
421 //The list we're looking at is beforeOthers, and contains a and will be before
422 //everything else in the final ist. If b is in the afterOthers list, then a cannot be before b.
423 if (_afterOthers.contains(fragNameB))
424 throw new IllegalStateException("Incorrect relationship: "+fragNameB+" after "+fragNameA);
425 else
426 return false; //b could be moved from noOthers list
427 }
428 }
429
430 return true; //a and b in the same list, a is after b
431 }
432
433 /**
434 * Insert the resource matching the fragName into the list of resources
435 * at the location indicated by index.
436 *
437 * @param list
438 * @param index
439 * @param fragName
440 */
441 protected void insert(List<Resource> list, int index, String fragName)
442 {
443 Resource jar = _metaData.getJarForFragment(fragName);
444 if (jar == null)
445 throw new IllegalStateException("No jar for insertion");
446
447 insert(list, index, jar);
448 }
449
450 protected void insert(List<Resource> list, int index, Resource resource)
451 {
452 if (list == null)
453 throw new IllegalStateException("List is null for insertion");
454
455 //add it at the end
456 if (index > list.size())
457 list.add(resource);
458 else
459 list.add(index, resource);
460 }
461
462 protected void remove (List<Resource> resources, Resource r)
463 {
464 if (resources == null)
465 return;
466 resources.remove(r);
467 }
468
469 protected int getIndexOf(List<Resource> resources, String fragmentName)
470 {
471 FragmentDescriptor fd = _metaData.getFragment(fragmentName);
472 if (fd == null)
473 return -1;
474
475
476 Resource r = _metaData.getJarForFragment(fragmentName);
477 if (r == null)
478 return -1;
479
480 return resources.indexOf(r);
481 }
482 }
483
484 }