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