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}