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