View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.maven.repository.metadata;
20  
21  import java.util.ArrayList;
22  import java.util.HashMap;
23  import java.util.List;
24  import java.util.Map;
25  import java.util.TreeSet;
26  
27  import org.apache.maven.artifact.ArtifactScopeEnum;
28  
29  /**
30   * maven dependency metadata graph
31   *
32   *
33   */
34  @Deprecated
35  public class MetadataGraph {
36      public static final int DEFAULT_VERTICES = 32;
37      public static final int DEFAULT_EDGES = 64;
38  
39      // flags to indicate the granularity of vertices
40      private boolean versionedVertices = false;
41      private boolean scopedVertices = false;
42      /**
43       * the entry point we started building the graph from
44       */
45      MetadataGraphVertex entry;
46  
47      // graph vertices
48      TreeSet<MetadataGraphVertex> vertices;
49  
50      /**
51       * incident and excident edges per node
52       */
53      Map<MetadataGraphVertex, List<MetadataGraphEdge>> incidentEdges;
54  
55      Map<MetadataGraphVertex, List<MetadataGraphEdge>> excidentEdges;
56  
57      /**
58       *  null in dirty graph, actual
59       *  scope for conflict-resolved graph
60       */
61      ArtifactScopeEnum scope;
62  
63      // ------------------------------------------------------------------------
64      /**
65       * init graph
66       */
67      public MetadataGraph(int nVertices) {
68          init(nVertices, 2 * nVertices);
69      }
70  
71      public MetadataGraph(int nVertices, int nEdges) {
72          init(nVertices, nEdges);
73      }
74      // ------------------------------------------------------------------------
75      /**
76       * construct a single vertex
77       */
78      public MetadataGraph(MetadataGraphVertex entry) throws MetadataResolutionException {
79          checkVertex(entry);
80          checkVertices(1);
81  
82          entry.setCompareVersion(versionedVertices);
83          entry.setCompareScope(scopedVertices);
84  
85          vertices.add(entry);
86          this.entry = entry;
87      }
88      // ------------------------------------------------------------------------
89      /**
90       * construct graph from a "dirty" tree
91       */
92      public MetadataGraph(MetadataTreeNode tree) throws MetadataResolutionException {
93          this(tree, false, false);
94      }
95      // ------------------------------------------------------------------------
96      /**
97       * construct graph from a "dirty" tree
98       *
99       * @param tree "dirty" tree root
100      * @param versionedVertices true if graph nodes should be versioned (different versions -&gt; different nodes)
101      * @param scopedVertices true if graph nodes should be versioned and scoped
102      * (different versions and/or scopes -&gt; different nodes)
103      *
104      */
105     public MetadataGraph(MetadataTreeNode tree, boolean versionedVertices, boolean scopedVertices)
106             throws MetadataResolutionException {
107         if (tree == null) {
108             throw new MetadataResolutionException("tree is null");
109         }
110 
111         setVersionedVertices(versionedVertices);
112         setScopedVertices(scopedVertices);
113 
114         this.versionedVertices = scopedVertices || versionedVertices;
115         this.scopedVertices = scopedVertices;
116 
117         int count = countNodes(tree);
118 
119         init(count, count + (count / 2));
120 
121         processTreeNodes(null, tree, 0, 0);
122     }
123     // ------------------------------------------------------------------------
124     private void processTreeNodes(MetadataGraphVertex parentVertex, MetadataTreeNode node, int depth, int pomOrder)
125             throws MetadataResolutionException {
126         if (node == null) {
127             return;
128         }
129 
130         MetadataGraphVertex vertex = new MetadataGraphVertex(node.md, versionedVertices, scopedVertices);
131         if (!vertices.contains(vertex)) {
132             vertices.add(vertex);
133         }
134 
135         if (parentVertex != null) // then create the edge
136         {
137             ArtifactMetadata md = node.getMd();
138             MetadataGraphEdge e =
139                     new MetadataGraphEdge(md.version, md.resolved, md.artifactScope, md.artifactUri, depth, pomOrder);
140             addEdge(parentVertex, vertex, e);
141         } else {
142             entry = vertex;
143         }
144 
145         MetadataTreeNode[] kids = node.getChildren();
146         if (kids == null || kids.length < 1) {
147             return;
148         }
149 
150         for (int i = 0; i < kids.length; i++) {
151             MetadataTreeNode n = kids[i];
152             processTreeNodes(vertex, n, depth + 1, i);
153         }
154     }
155     // ------------------------------------------------------------------------
156     public MetadataGraphVertex findVertex(ArtifactMetadata md) {
157         if (md == null || vertices == null || vertices.size() < 1) {
158             return null;
159         }
160 
161         MetadataGraphVertex v = new MetadataGraphVertex(md);
162         v.setCompareVersion(versionedVertices);
163         v.setCompareScope(scopedVertices);
164 
165         for (MetadataGraphVertex gv : vertices) {
166             if (gv.equals(v)) {
167                 return gv;
168             }
169         }
170 
171         return null;
172     }
173     // ------------------------------------------------------------------------
174     public MetadataGraphVertex addVertex(ArtifactMetadata md) {
175         if (md == null) {
176             return null;
177         }
178 
179         checkVertices();
180 
181         MetadataGraphVertex v = findVertex(md);
182         if (v != null) {
183             return v;
184         }
185 
186         v = new MetadataGraphVertex(md);
187 
188         v.setCompareVersion(versionedVertices);
189         v.setCompareScope(scopedVertices);
190 
191         vertices.add(v);
192         return v;
193     }
194     // ------------------------------------------------------------------------
195     /**
196      * init graph
197      */
198     private void init(int nVertices, int nEdges) {
199         int nV = nVertices;
200         if (nVertices < 1) {
201             nV = 1;
202         }
203 
204         checkVertices(nV);
205 
206         int nE = nVertices;
207         if (nEdges <= nV) {
208             nE = 2 * nE;
209         }
210 
211         checkEdges(nE);
212     }
213 
214     private void checkVertices() {
215         checkVertices(DEFAULT_VERTICES);
216     }
217 
218     private void checkVertices(int nVertices) {
219         if (vertices == null) {
220             vertices = new TreeSet<>();
221         }
222     }
223 
224     private void checkEdges() {
225         int count = DEFAULT_EDGES;
226 
227         if (vertices != null) {
228             count = vertices.size() + vertices.size() / 2;
229         }
230 
231         checkEdges(count);
232     }
233 
234     private void checkEdges(int nEdges) {
235         if (incidentEdges == null) {
236             incidentEdges = new HashMap<>(nEdges);
237         }
238         if (excidentEdges == null) {
239             excidentEdges = new HashMap<>(nEdges);
240         }
241     }
242     // ------------------------------------------------------------------------
243     private static void checkVertex(MetadataGraphVertex v) throws MetadataResolutionException {
244         if (v == null) {
245             throw new MetadataResolutionException("null vertex");
246         }
247         if (v.getMd() == null) {
248             throw new MetadataResolutionException("vertex without metadata");
249         }
250     }
251     // ------------------------------------------------------------------------
252     private static void checkEdge(MetadataGraphEdge e) throws MetadataResolutionException {
253         if (e == null) {
254             throw new MetadataResolutionException("badly formed edge");
255         }
256     }
257     // ------------------------------------------------------------------------
258     public List<MetadataGraphEdge> getEdgesBetween(MetadataGraphVertex vFrom, MetadataGraphVertex vTo) {
259         List<MetadataGraphEdge> edges = getIncidentEdges(vTo);
260         if (edges == null || edges.isEmpty()) {
261             return null;
262         }
263 
264         List<MetadataGraphEdge> res = new ArrayList<>(edges.size());
265 
266         for (MetadataGraphEdge e : edges) {
267             if (e.getSource().equals(vFrom)) {
268                 res.add(e);
269             }
270         }
271 
272         return res;
273     }
274     // ------------------------------------------------------------------------
275     public MetadataGraph addEdge(MetadataGraphVertex vFrom, MetadataGraphVertex vTo, MetadataGraphEdge e)
276             throws MetadataResolutionException {
277         checkVertex(vFrom);
278         checkVertex(vTo);
279 
280         checkVertices();
281 
282         checkEdge(e);
283         checkEdges();
284 
285         e.setSource(vFrom);
286         e.setTarget(vTo);
287 
288         vFrom.setCompareVersion(versionedVertices);
289         vFrom.setCompareScope(scopedVertices);
290 
291         List<MetadataGraphEdge> exList = excidentEdges.computeIfAbsent(vFrom, k -> new ArrayList<>());
292 
293         if (!exList.contains(e)) {
294             exList.add(e);
295         }
296 
297         List<MetadataGraphEdge> inList = incidentEdges.computeIfAbsent(vTo, k -> new ArrayList<>());
298 
299         if (!inList.contains(e)) {
300             inList.add(e);
301         }
302 
303         return this;
304     }
305     // ------------------------------------------------------------------------
306     public MetadataGraph removeVertex(MetadataGraphVertex v) {
307         if (vertices != null && v != null) {
308             vertices.remove(v);
309         }
310 
311         if (incidentEdges != null) {
312             incidentEdges.remove(v);
313         }
314 
315         if (excidentEdges != null) {
316             excidentEdges.remove(v);
317         }
318 
319         return this;
320     }
321     // ------------------------------------------------------------------------
322     private static int countNodes(MetadataTreeNode tree) {
323         if (tree == null) {
324             return 0;
325         }
326 
327         int count = 1;
328         MetadataTreeNode[] kids = tree.getChildren();
329         if (kids == null || kids.length < 1) {
330             return count;
331         }
332         for (MetadataTreeNode n : kids) {
333             count += countNodes(n);
334         }
335 
336         return count;
337     }
338 
339     // ------------------------------------------------------------------------
340     public MetadataGraphVertex getEntry() {
341         return entry;
342     }
343 
344     public void setEntry(MetadataGraphVertex entry) {
345         this.entry = entry;
346     }
347 
348     public TreeSet<MetadataGraphVertex> getVertices() {
349         return vertices;
350     }
351 
352     public List<MetadataGraphEdge> getIncidentEdges(MetadataGraphVertex vertex) {
353         checkEdges();
354         return incidentEdges.get(vertex);
355     }
356 
357     public List<MetadataGraphEdge> getExcidentEdges(MetadataGraphVertex vertex) {
358         checkEdges();
359         return excidentEdges.get(vertex);
360     }
361 
362     public boolean isVersionedVertices() {
363         return versionedVertices;
364     }
365 
366     public void setVersionedVertices(boolean versionedVertices) {
367         this.versionedVertices = versionedVertices;
368     }
369 
370     public boolean isScopedVertices() {
371         return scopedVertices;
372     }
373 
374     public void setScopedVertices(boolean scopedVertices) {
375         this.scopedVertices = scopedVertices;
376 
377         // scoped graph is versioned by definition
378         if (scopedVertices) {
379             versionedVertices = true;
380         }
381     }
382 
383     public ArtifactScopeEnum getScope() {
384         return scope;
385     }
386 
387     public void setScope(ArtifactScopeEnum scope) {
388         this.scope = scope;
389     }
390 
391     // ------------------------------------------------------------------------
392     public boolean isEmpty() {
393         return entry == null || vertices == null || vertices.isEmpty();
394     }
395 
396     // ------------------------------------------------------------------------
397     public boolean isEmptyEdges() {
398         return isEmpty() || incidentEdges == null || incidentEdges.isEmpty();
399     }
400     // ------------------------------------------------------------------------
401     @Override
402     public String toString() {
403         if (isEmpty()) {
404             return "empty";
405         }
406         StringBuilder sb = new StringBuilder(512);
407         for (MetadataGraphVertex v : vertices) {
408             sb.append("Vertex:  ").append(v.getMd().toString()).append('\n');
409             List<MetadataGraphEdge> ins = getIncidentEdges(v);
410             if (ins != null) {
411                 for (MetadataGraphEdge e : ins) {
412                     sb.append("       from :  ").append(e.toString()).append('\n');
413                 }
414             } else {
415                 sb.append("      no entries\n");
416             }
417 
418             List<MetadataGraphEdge> outs = getExcidentEdges(v);
419             if (outs != null) {
420                 for (MetadataGraphEdge e : outs) {
421                     sb.append("        to :  ").append(e.toString()).append('\n');
422                 }
423             } else {
424                 sb.append("      no exit\n");
425             }
426 
427             sb.append("-------------------------------------------------\n");
428         }
429         sb.append("=============================================================\n");
430         return sb.toString();
431     }
432 
433     // ------------------------------------------------------------------------
434     // ------------------------------------------------------------------------
435 }