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