View Javadoc

1   package org.apache.maven.repository.metadata;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *  http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
20   */
21  
22  import java.util.ArrayList;
23  import java.util.HashMap;
24  import java.util.List;
25  import java.util.Map;
26  import java.util.TreeSet;
27  
28  import org.apache.maven.artifact.ArtifactScopeEnum;
29  
30  /**
31   * maven dependency metadata graph
32   *
33   * @author <a href="oleg@codehaus.org">Oleg Gusakov</a>
34   *
35   */
36  public class MetadataGraph
37  {
38      public static final int DEFAULT_VERTICES = 32;
39      public static final int DEFAULT_EDGES    = 64;
40  
41      // flags to indicate the granularity of vertices
42      private boolean versionedVertices = false;
43      private boolean scopedVertices    = false;
44      /**
45      * the entry point we started building the graph from
46      */
47      MetadataGraphVertex entry;
48  
49      // graph vertices
50      TreeSet<MetadataGraphVertex> vertices;
51  
52      /**
53       * incident and excident edges per node
54       */
55      Map<MetadataGraphVertex, List<MetadataGraphEdge>> incidentEdges;
56      Map<MetadataGraphVertex, List<MetadataGraphEdge>> excidentEdges;
57  
58      /**
59       *  null in dirty graph, actual
60       *  scope for conflict-resolved graph
61       */
62      ArtifactScopeEnum scope;
63  
64      //------------------------------------------------------------------------
65      /**
66       * init graph
67       */
68      public MetadataGraph( int nVertices )
69      {
70          init( nVertices, 2 * nVertices );
71      }
72      public MetadataGraph( int nVertices, int nEdges )
73      {
74          init( nVertices, nEdges );
75      }
76      //------------------------------------------------------------------------
77      /**
78       * construct a single vertex
79       */
80      public MetadataGraph( MetadataGraphVertex entry )
81          throws MetadataResolutionException
82      {
83          checkVertex( entry );
84          checkVertices( 1 );
85  
86          entry.setCompareVersion( versionedVertices );
87          entry.setCompareScope( scopedVertices );
88  
89          vertices.add( entry );
90          this.entry = entry;
91      }
92      //------------------------------------------------------------------------
93      /**
94       * construct graph from a "dirty" tree
95       */
96      public MetadataGraph( MetadataTreeNode tree )
97          throws MetadataResolutionException
98      {
99          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 }