001 package org.apache.maven.repository.metadata;
002
003 /*
004 * Licensed to the Apache Software Foundation (ASF) under one
005 * or more contributor license agreements. See the NOTICE file
006 * distributed with this work for additional information
007 * regarding copyright ownership. The ASF licenses this file
008 * to you under the Apache License, Version 2.0 (the
009 * "License"); you may not use this file except in compliance
010 * with the License. You may obtain a copy of the License at
011 *
012 * http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing,
015 * software distributed under the License is distributed on an
016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017 * KIND, either express or implied. See the License for the
018 * specific language governing permissions and limitations
019 * under the License.
020 */
021
022 import java.util.ArrayList;
023 import java.util.HashMap;
024 import java.util.List;
025 import java.util.Map;
026 import java.util.TreeSet;
027
028 import org.apache.maven.artifact.ArtifactScopeEnum;
029
030 /**
031 * maven dependency metadata graph
032 *
033 * @author <a href="oleg@codehaus.org">Oleg Gusakov</a>
034 *
035 */
036 public class MetadataGraph
037 {
038 public static final int DEFAULT_VERTICES = 32;
039 public static final int DEFAULT_EDGES = 64;
040
041 // flags to indicate the granularity of vertices
042 private boolean versionedVertices = false;
043 private boolean scopedVertices = false;
044 /**
045 * the entry point we started building the graph from
046 */
047 MetadataGraphVertex entry;
048
049 // graph vertices
050 TreeSet<MetadataGraphVertex> vertices;
051
052 /**
053 * incident and excident edges per node
054 */
055 Map<MetadataGraphVertex, List<MetadataGraphEdge>> incidentEdges;
056 Map<MetadataGraphVertex, List<MetadataGraphEdge>> excidentEdges;
057
058 /**
059 * null in dirty graph, actual
060 * scope for conflict-resolved graph
061 */
062 ArtifactScopeEnum scope;
063
064 //------------------------------------------------------------------------
065 /**
066 * init graph
067 */
068 public MetadataGraph( int nVertices )
069 {
070 init( nVertices, 2 * nVertices );
071 }
072 public MetadataGraph( int nVertices, int nEdges )
073 {
074 init( nVertices, nEdges );
075 }
076 //------------------------------------------------------------------------
077 /**
078 * construct a single vertex
079 */
080 public MetadataGraph( MetadataGraphVertex entry )
081 throws MetadataResolutionException
082 {
083 checkVertex( entry );
084 checkVertices( 1 );
085
086 entry.setCompareVersion( versionedVertices );
087 entry.setCompareScope( scopedVertices );
088
089 vertices.add( entry );
090 this.entry = entry;
091 }
092 //------------------------------------------------------------------------
093 /**
094 * construct graph from a "dirty" tree
095 */
096 public MetadataGraph( MetadataTreeNode tree )
097 throws MetadataResolutionException
098 {
099 this( tree, false, false );
100 }
101 //------------------------------------------------------------------------
102 /**
103 * construct graph from a "dirty" tree
104 *
105 * @param tree "dirty" tree root
106 * @param versionedVertices true if graph nodes should be versioned (different versions -> different nodes)
107 * @param scopedVertices true if graph nodes should be versioned and scoped (different versions and/or scopes -> different nodes)
108 *
109 */
110 public MetadataGraph( MetadataTreeNode tree, boolean versionedVertices, boolean scopedVertices )
111 throws MetadataResolutionException
112 {
113 if ( tree == null )
114 {
115 throw new MetadataResolutionException( "tree is null" );
116 }
117
118 setVersionedVertices( versionedVertices );
119 setScopedVertices( scopedVertices );
120
121 this.versionedVertices = scopedVertices || versionedVertices;
122 this.scopedVertices = scopedVertices;
123
124 int count = countNodes( tree );
125
126 init( count, count + ( count / 2 ) );
127
128 processTreeNodes( null, tree, 0, 0 );
129 }
130 //------------------------------------------------------------------------
131 private void processTreeNodes( MetadataGraphVertex parentVertex, MetadataTreeNode node, int depth, int pomOrder )
132 throws MetadataResolutionException
133 {
134 if ( node == null )
135 {
136 return;
137 }
138
139 MetadataGraphVertex vertex = new MetadataGraphVertex( node.md, versionedVertices, scopedVertices );
140 if ( !vertices.contains( vertex ) )
141 {
142 vertices.add( vertex );
143 }
144
145 if ( parentVertex != null ) // then create the edge
146 {
147 ArtifactMetadata md = node.getMd();
148 MetadataGraphEdge e =
149 new MetadataGraphEdge( md.version, md.resolved, md.artifactScope, md.artifactUri, depth, pomOrder );
150 addEdge( parentVertex, vertex, e );
151 }
152 else
153 {
154 entry = vertex;
155 }
156
157 MetadataTreeNode[] kids = node.getChildren();
158 if ( kids == null || kids.length < 1 )
159 {
160 return;
161 }
162
163 for ( int i = 0; i < kids.length; i++ )
164 {
165 MetadataTreeNode n = kids[i];
166 processTreeNodes( vertex, n, depth + 1, i );
167 }
168 }
169 //------------------------------------------------------------------------
170 public MetadataGraphVertex findVertex( ArtifactMetadata md )
171 {
172 if ( md == null || vertices == null || vertices.size() < 1 )
173 {
174 return null;
175 }
176
177 MetadataGraphVertex v = new MetadataGraphVertex( md );
178 v.setCompareVersion( versionedVertices );
179 v.setCompareScope( scopedVertices );
180
181 for ( MetadataGraphVertex gv : vertices )
182 {
183 if ( gv.equals( v ) )
184 {
185 return gv;
186 }
187 }
188
189 return null;
190 }
191 //------------------------------------------------------------------------
192 public MetadataGraphVertex addVertex( ArtifactMetadata md )
193 {
194 if ( md == null )
195 {
196 return null;
197 }
198
199 checkVertices();
200
201 MetadataGraphVertex v = findVertex( md );
202 if ( v != null )
203 {
204 return v;
205 }
206
207 v = new MetadataGraphVertex( md );
208
209 v.setCompareVersion( versionedVertices );
210 v.setCompareScope( scopedVertices );
211
212 vertices.add( v );
213 return v;
214 }
215 //------------------------------------------------------------------------
216 /**
217 * init graph
218 */
219 private void init( int nVertices, int nEdges )
220 {
221 int nV = nVertices;
222 if ( nVertices < 1 )
223 {
224 nV = 1;
225 }
226
227 checkVertices( nV );
228
229 int nE = nVertices;
230 if ( nEdges <= nV )
231 {
232 nE = 2 * nE;
233 }
234
235 checkEdges( nE );
236 }
237
238 private void checkVertices()
239 {
240 checkVertices( DEFAULT_VERTICES );
241 }
242
243 private void checkVertices( int nVertices )
244 {
245 if ( vertices == null )
246 {
247 vertices = new TreeSet<MetadataGraphVertex>();
248 }
249 }
250 private void checkEdges()
251 {
252 int count = DEFAULT_EDGES;
253
254 if ( vertices != null )
255 {
256 count = vertices.size() + vertices.size() / 2;
257 }
258
259 checkEdges( count );
260 }
261 private void checkEdges( int nEdges )
262 {
263 if ( incidentEdges == null )
264 {
265 incidentEdges = new HashMap<MetadataGraphVertex, List<MetadataGraphEdge>>( nEdges );
266 }
267 if ( excidentEdges == null )
268 {
269 excidentEdges = new HashMap<MetadataGraphVertex, List<MetadataGraphEdge>>( nEdges );
270 }
271 }
272 //------------------------------------------------------------------------
273 private static void checkVertex( MetadataGraphVertex v )
274 throws MetadataResolutionException
275 {
276 if ( v == null )
277 {
278 throw new MetadataResolutionException( "null vertex" );
279 }
280 if ( v.getMd() == null )
281 {
282 throw new MetadataResolutionException( "vertex without metadata" );
283 }
284 }
285 //------------------------------------------------------------------------
286 private static void checkEdge( MetadataGraphEdge e )
287 throws MetadataResolutionException
288 {
289 if ( e == null )
290 {
291 throw new MetadataResolutionException( "badly formed edge" );
292 }
293 }
294 //------------------------------------------------------------------------
295 public List<MetadataGraphEdge> getEdgesBetween( MetadataGraphVertex vFrom, MetadataGraphVertex vTo )
296 {
297 List<MetadataGraphEdge> edges = getIncidentEdges( vTo );
298 if ( edges == null || edges.isEmpty() )
299 {
300 return null;
301 }
302
303 List<MetadataGraphEdge> res = new ArrayList<MetadataGraphEdge>( edges.size() );
304
305 for ( MetadataGraphEdge e : edges )
306 {
307 if ( e.getSource().equals( vFrom ) )
308 {
309 res.add( e );
310 }
311 }
312
313 return res;
314 }
315 //------------------------------------------------------------------------
316 public MetadataGraph addEdge( MetadataGraphVertex vFrom, MetadataGraphVertex vTo, MetadataGraphEdge e )
317 throws MetadataResolutionException
318 {
319 checkVertex( vFrom );
320 checkVertex( vTo );
321
322 checkVertices();
323
324 checkEdge( e );
325 checkEdges();
326
327 e.setSource( vFrom );
328 e.setTarget( vTo );
329
330 vFrom.setCompareVersion( versionedVertices );
331 vFrom.setCompareScope( scopedVertices );
332
333 List<MetadataGraphEdge> exList = excidentEdges.get( vFrom );
334 if ( exList == null )
335 {
336 exList = new ArrayList<MetadataGraphEdge>();
337 excidentEdges.put( vFrom, exList );
338 }
339
340 if ( !exList.contains( e ) )
341 {
342 exList.add( e );
343 }
344
345 List<MetadataGraphEdge> inList = incidentEdges.get( vTo );
346 if ( inList == null )
347 {
348 inList = new ArrayList<MetadataGraphEdge>();
349 incidentEdges.put( vTo, inList );
350 }
351
352 if ( !inList.contains( e ) )
353 {
354 inList.add( e );
355 }
356
357 return this;
358 }
359 //------------------------------------------------------------------------
360 public MetadataGraph removeVertex( MetadataGraphVertex v )
361 {
362 if ( vertices != null && v != null )
363 {
364 vertices.remove( v );
365 }
366
367 if ( incidentEdges != null )
368 {
369 incidentEdges.remove( v );
370 }
371
372 if ( excidentEdges != null )
373 {
374 excidentEdges.remove( v );
375 }
376
377 return this;
378
379 }
380 //------------------------------------------------------------------------
381 private static int countNodes( MetadataTreeNode tree )
382 {
383 if ( tree == null )
384 {
385 return 0;
386 }
387
388 int count = 1;
389 MetadataTreeNode[] kids = tree.getChildren();
390 if ( kids == null || kids.length < 1 )
391 {
392 return count;
393 }
394 for ( MetadataTreeNode n : kids )
395 {
396 count += countNodes( n );
397 }
398
399 return count;
400 }
401
402 //------------------------------------------------------------------------
403 public MetadataGraphVertex getEntry()
404 {
405 return entry;
406 }
407
408 public void setEntry( MetadataGraphVertex entry )
409 {
410 this.entry = entry;
411 }
412
413 public TreeSet<MetadataGraphVertex> getVertices()
414 {
415 return vertices;
416 }
417
418 public List<MetadataGraphEdge> getIncidentEdges( MetadataGraphVertex vertex )
419 {
420 checkEdges();
421 return incidentEdges.get( vertex );
422 }
423
424 public List<MetadataGraphEdge> getExcidentEdges( MetadataGraphVertex vertex )
425 {
426 checkEdges();
427 return excidentEdges.get( vertex );
428 }
429
430 public boolean isVersionedVertices()
431 {
432 return versionedVertices;
433 }
434
435 public void setVersionedVertices( boolean versionedVertices )
436 {
437 this.versionedVertices = versionedVertices;
438 }
439
440 public boolean isScopedVertices()
441 {
442 return scopedVertices;
443 }
444
445 public void setScopedVertices( boolean scopedVertices )
446 {
447 this.scopedVertices = scopedVertices;
448
449 // scoped graph is versioned by definition
450 if ( scopedVertices )
451 {
452 versionedVertices = true;
453 }
454 }
455
456 public ArtifactScopeEnum getScope()
457 {
458 return scope;
459 }
460
461 public void setScope( ArtifactScopeEnum scope )
462 {
463 this.scope = scope;
464 }
465
466 // ------------------------------------------------------------------------
467 public boolean isEmpty()
468 {
469 return entry == null || vertices == null || vertices.isEmpty();
470 }
471
472 //------------------------------------------------------------------------
473 public boolean isEmptyEdges()
474 {
475 return isEmpty() || incidentEdges == null || incidentEdges.isEmpty();
476 }
477 //------------------------------------------------------------------------
478 @Override
479 public String toString()
480 {
481 StringBuilder sb = new StringBuilder( 512 );
482 if ( isEmpty() )
483 {
484 return "empty";
485 }
486 for ( MetadataGraphVertex v : vertices )
487 {
488 sb.append( "Vertex: " + v.getMd().toString() + "\n" );
489 List<MetadataGraphEdge> ins = getIncidentEdges( v );
490 if ( ins != null )
491 {
492 for ( MetadataGraphEdge e : ins )
493 {
494 sb.append( " from : " + e.toString() + "\n" );
495 }
496 }
497 else
498 {
499 sb.append( " no entries\n" );
500 }
501
502 List<MetadataGraphEdge> outs = getExcidentEdges( v );
503 if ( outs != null )
504 {
505 for ( MetadataGraphEdge e : outs )
506 {
507 sb.append( " to : " + e.toString() + "\n" );
508 }
509 }
510 else
511 {
512 sb.append( " no exit\n" );
513 }
514
515 sb.append( "-------------------------------------------------\n" );
516 }
517 sb.append( "=============================================================\n" );
518 return sb.toString();
519 }
520
521 //------------------------------------------------------------------------
522 //------------------------------------------------------------------------
523 }