BUG-4688: eliminate SimpleDateFormatUtil.DEFAULT_DATE_REV
[yangtools.git] / yang / yang-model-util / src / main / java / org / opendaylight / yangtools / yang / model / util / ModuleDependencySort.java
1 /*
2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
3  *
4  * This program and the accompanying materials are made available under the
5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6  * and is available at http://www.eclipse.org/legal/epl-v10.html
7  */
8 package org.opendaylight.yangtools.yang.model.util;
9
10 import com.google.common.annotations.Beta;
11 import com.google.common.collect.HashBasedTable;
12 import com.google.common.collect.Lists;
13 import com.google.common.collect.Table;
14 import java.net.URI;
15 import java.util.Collection;
16 import java.util.Date;
17 import java.util.HashMap;
18 import java.util.HashSet;
19 import java.util.List;
20 import java.util.Map;
21 import java.util.Objects;
22 import java.util.Optional;
23 import org.opendaylight.yangtools.util.TopologicalSort;
24 import org.opendaylight.yangtools.util.TopologicalSort.Node;
25 import org.opendaylight.yangtools.util.TopologicalSort.NodeImpl;
26 import org.opendaylight.yangtools.yang.common.SimpleDateFormatUtil;
27 import org.opendaylight.yangtools.yang.common.YangVersion;
28 import org.opendaylight.yangtools.yang.model.api.Module;
29 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
30 import org.slf4j.Logger;
31 import org.slf4j.LoggerFactory;
32
33 /**
34  * Creates a module dependency graph from provided {@link Module}s and provides a {@link #sort(Collection)} method.
35  * It is topological sort and returns modules in order in which they should be processed (e.g. if A imports B, sort
36  * returns {B, A}).
37  */
38 @Beta
39 public final class ModuleDependencySort {
40     private static final Logger LOG = LoggerFactory.getLogger(ModuleDependencySort.class);
41
42     /**
43      * It is not desirable to instance this class.
44      */
45     private ModuleDependencySort() {
46         throw new UnsupportedOperationException();
47     }
48
49     /**
50      * Topological sort of module dependency graph.
51      *
52      * @param modules YANG modules
53      * @return Sorted list of Modules. Modules can be further processed in returned order.
54      * @throws IllegalArgumentException when provided modules are not consistent.
55      */
56     public static List<Module> sort(final Collection<Module> modules) {
57         return sort((Iterable<Module>)modules);
58     }
59
60     /**
61      * Topological sort of module dependency graph.
62      *
63      * @param modules YANG modules
64      * @return Sorted list of Modules. Modules can be further processed in
65      *         returned order.
66      * @throws IllegalArgumentException when provided modules are not consistent.
67      *
68      * @deprecated Use {@link #sort(Collection)} instead.
69      */
70     @Deprecated
71     public static List<Module> sort(final Iterable<Module> modules) {
72         final List<Node> sorted = sortInternal(modules);
73         // Cast to Module from Node and return
74         return Lists.transform(sorted, input -> input == null ? null : ((ModuleNodeImpl) input).getReference());
75     }
76
77     private static List<Node> sortInternal(final Iterable<Module> modules) {
78         final Table<String, Optional<Date>, ModuleNodeImpl> moduleGraph = createModuleGraph(modules);
79         return TopologicalSort.sort(new HashSet<>(moduleGraph.values()));
80     }
81
82     private static Table<String, Optional<Date>, ModuleNodeImpl> createModuleGraph(final Iterable<Module> builders) {
83         final Table<String, Optional<Date>, ModuleNodeImpl> moduleGraph = HashBasedTable.create();
84
85         processModules(moduleGraph, builders);
86         processDependencies(moduleGraph, builders);
87
88         return moduleGraph;
89     }
90
91     /**
92      * Extract module:revision from modules.
93      */
94     private static void processDependencies(final Table<String, Optional<Date>, ModuleNodeImpl> moduleGraph,
95             final Iterable<Module> mmbs) {
96         final Map<URI, Module> allNS = new HashMap<>();
97
98         // Create edges in graph
99         for (final Module module : mmbs) {
100             final Map<String, Date> imported = new HashMap<>();
101             final String fromName = module.getName();
102             final URI ns = module.getNamespace();
103             final Date fromRevision = module.getRevision();
104
105             // check for existence of module with same namespace
106             final Module prev = allNS.putIfAbsent(ns, module);
107             if (prev != null) {
108                 final String name = prev.getName();
109                 if (!fromName.equals(name)) {
110                     LOG.warn("Error while sorting module [{}, {}]: module with same namespace ({}) already loaded:"
111                         + " [{}, {}]", fromName, fromRevision, ns, name, prev.getRevision());
112                 }
113             }
114
115             // no need to check if other Type of object, check is performed in process modules
116             for (final ModuleImport imprt : module.getImports()) {
117                 final String toName = imprt.getModuleName();
118                 final Date toRevision = imprt.getRevision();
119
120                 final ModuleNodeImpl from = moduleGraph.get(fromName, Optional.ofNullable(fromRevision));
121                 final ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, fromName, fromRevision, toName,
122                     toRevision);
123
124                 /*
125                  * If it is an yang 1 module, check imports: If module is imported twice with different
126                  * revisions then throw exception
127                  */
128                 if (module.getYangVersion() == YangVersion.VERSION_1) {
129                     final Date impRevision = imported.get(toName);
130                     if (impRevision != null && !impRevision.equals(toRevision) && toRevision != null) {
131                         throw new IllegalArgumentException(String.format(
132                             "Module:%s imported twice with different revisions:%s, %s", toName,
133                             formatRevDate(impRevision), formatRevDate(toRevision)));
134                     }
135                 }
136
137                 imported.put(toName, toRevision);
138
139                 from.addEdge(to);
140             }
141         }
142     }
143
144     /**
145      * Get imported module by its name and revision from moduleGraph.
146      */
147     private static ModuleNodeImpl getModuleByNameAndRevision(
148             final Table<String, Optional<Date>, ModuleNodeImpl> moduleGraph,
149             final String fromName, final Date fromRevision, final String toName, final Date toRevision) {
150
151         final ModuleNodeImpl exact = moduleGraph.get(toName, Optional.ofNullable(toRevision));
152         if (exact != null) {
153             return exact;
154         }
155
156         // If revision is not specified in import, but module exists with different revisions, take first one
157         if (toRevision == null) {
158             final Map<Optional<Date>, ModuleNodeImpl> modulerevs = moduleGraph.row(toName);
159
160             if (!modulerevs.isEmpty()) {
161                 final ModuleNodeImpl first = modulerevs.values().iterator().next();
162                 if (LOG.isTraceEnabled()) {
163                     LOG.trace("Import:{}:{} by module:{}:{} does not specify revision, using:{}:{}"
164                             + " for module dependency sort", toName, formatRevDate(toRevision), fromName,
165                             formatRevDate(fromRevision), first.getName(), formatRevDate(first.getRevision()));
166                 }
167                 return first;
168             }
169         }
170
171         LOG.warn("Not existing module imported:{}:{} by:{}:{}", toName, formatRevDate(toRevision), fromName,
172             formatRevDate(fromRevision));
173         LOG.warn("Available models: {}", moduleGraph);
174         throw new IllegalArgumentException(String.format("Not existing module imported:%s:%s by:%s:%s", toName,
175             formatRevDate(toRevision), fromName, formatRevDate(fromRevision)));
176     }
177
178     /**
179      * Extract dependencies from modules to fill dependency graph.
180      */
181     private static void processModules(final Table<String, Optional<Date>, ModuleNodeImpl> moduleGraph,
182             final Iterable<Module> modules) {
183
184         // Process nodes
185         for (final Module momb : modules) {
186
187             final String name = momb.getName();
188             final Optional<Date> rev = Optional.ofNullable(momb.getRevision());
189
190             final Map<Optional<Date>, ModuleNodeImpl> revs = moduleGraph.row(name);
191             if (revs.containsKey(rev)) {
192                 throw new IllegalArgumentException(String.format("Module:%s with revision:%s declared twice", name,
193                     formatRevDate(rev.orElse(null))));
194             }
195
196             revs.put(rev, new ModuleNodeImpl(name, rev.orElse(null), momb));
197         }
198     }
199
200     private static String formatRevDate(final Date rev) {
201         return rev == null ? "default" : SimpleDateFormatUtil.getRevisionFormat().format(rev);
202     }
203
204     private static final class ModuleNodeImpl extends NodeImpl {
205         private final String name;
206         private final Date revision;
207         private final Module originalObject;
208
209         ModuleNodeImpl(final String name, final Date revision, final Module module) {
210             this.name = name;
211             this.revision = revision;
212             this.originalObject = module;
213         }
214
215         String getName() {
216             return name;
217         }
218
219         Date getRevision() {
220             return revision;
221         }
222
223         @Override
224         public int hashCode() {
225             final int prime = 31;
226             int result = 1;
227             result = prime * result + Objects.hashCode(name);
228             result = prime * result + Objects.hashCode(revision);
229             return result;
230         }
231
232         @Override
233         public boolean equals(final Object obj) {
234             if (this == obj) {
235                 return true;
236             }
237             if (obj == null) {
238                 return false;
239             }
240             if (getClass() != obj.getClass()) {
241                 return false;
242             }
243             final ModuleNodeImpl other = (ModuleNodeImpl) obj;
244             if (name == null) {
245                 if (other.name != null) {
246                     return false;
247                 }
248             } else if (!name.equals(other.name)) {
249                 return false;
250             }
251             if (revision == null) {
252                 if (other.revision != null) {
253                     return false;
254                 }
255             } else if (!revision.equals(other.revision)) {
256                 return false;
257             }
258             return true;
259         }
260
261         @Override
262         public String toString() {
263             return "Module [name=" + name + ", revision=" + formatRevDate(revision) + "]";
264         }
265
266         public Module getReference() {
267             return originalObject;
268         }
269     }
270 }