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