001package 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
022import java.util.ArrayList;
023import java.util.HashMap;
024import java.util.List;
025import java.util.Map;
026import java.util.TreeSet;
027
028import 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 */
036public 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:  " ).append( v.getMd().toString() ).append( "\n" );
489            List<MetadataGraphEdge> ins = getIncidentEdges( v );
490            if ( ins != null )
491            {
492                for ( MetadataGraphEdge e : ins )
493                {
494                    sb.append( "       from :  " ).append( e.toString() ).append( "\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 :  " ).append( e.toString() ).append( "\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}