source: default/trunk/de.ugoe.cs.swe.bnftools.ebnf/src/de/ugoe/cs/swe/bnftools/validation/EbnfJavaValidator.java @ 50

Last change on this file since 50 was 50, checked in by zeiss, 13 years ago
  • Property svn:mime-type set to text/plain
File size: 18.5 KB
Line 
1package de.ugoe.cs.swe.bnftools.validation;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.HashSet;
6import java.util.Iterator;
7import java.util.List;
8import java.util.Set;
9import java.util.Stack;
10
11import org.eclipse.emf.common.util.EList;
12import org.eclipse.emf.common.util.URI;
13import org.eclipse.emf.ecore.EObject;
14import org.eclipse.emf.ecore.resource.Resource;
15import org.eclipse.xtext.parsetree.AbstractNode;
16import org.eclipse.xtext.parsetree.CompositeNode;
17import org.eclipse.xtext.parsetree.LeafNode;
18import org.eclipse.xtext.parsetree.NodeUtil;
19import org.eclipse.xtext.resource.IResourceDescriptions;
20import org.eclipse.xtext.resource.XtextResource;
21import org.eclipse.xtext.resource.XtextResourceSet;
22import org.eclipse.xtext.validation.Check;
23import org.eclipse.xtext.validation.CheckType;
24
25import com.google.inject.Inject;
26
27import de.ugoe.cs.swe.bnftools.analysis.EbnfAnalysisUtils;
28import de.ugoe.cs.swe.bnftools.ebnf.BnfEntry;
29import de.ugoe.cs.swe.bnftools.ebnf.DefinitionList;
30import de.ugoe.cs.swe.bnftools.ebnf.EtsiBnf;
31import de.ugoe.cs.swe.bnftools.ebnf.ExtRule;
32import de.ugoe.cs.swe.bnftools.ebnf.Import;
33import de.ugoe.cs.swe.bnftools.ebnf.Rule;
34import de.ugoe.cs.swe.bnftools.ebnf.SingleDefinition;
35
36public class EbnfJavaValidator extends AbstractEbnfJavaValidator {
37
38        @Inject
39        IResourceDescriptions resourceDescriptions;
40
41        public static final String ruleReferencedOneDescription = "The rule is only referenced by one other rule";
42        public static final String passthroughRuleDescription = "The rule is a passthrough rule";
43        public static final String unreferencedPassthroughRuleDescription = "The rule is an unreferenced passthrough rule";
44        public static final String unusedRuleDescription = "The rule is not referenced anywhere";
45        public static final String equalAlternativeDescription = "The rule contains equal alternatives";
46        public static final String duplicateRulesDescription = "The rule is a duplicate";
47        public static final String duplicateSubRulesDescription = "A part of rule is a duplicate";
48        public static final String packageConsistencyCheckRuleMissingDescription = "Rule has been removed or renamed in the updated grammar. The package rule is therefore now an additional rule instead of a replacement rule. The package rule might therefore be inconsistent with the updated core grammar.";
49        public static final String packageConsistencyCheckRuleDifferentDescription = "Corresponding core grammar rule has been changed in updated grammar. The package rule might have become inconsistent with the updated core grammar.";
50        public static final String packageConsistencyCheckCorrespondingRuleMissingDescription = "Corresponding rule is missing in core grammar. Rule has been manually altered in the delta grammar (delta grammar is outdated) or the /core and /update flags are somehow switched.";
51
52        public static boolean checkReferencedOnlyOnce = false;
53        public static boolean checkPassthroughRule = false;
54        public static boolean checkUnusedRule = false;
55        public static boolean checkEqualAlternative = false;
56        public static boolean checkDuplicateRules = false;
57        public static boolean checkSubruleDuplicates = false;
58        public static boolean checkUpdatedGrammarConsistency = false;
59
60        // ----------------------------------------------------------------------------------------------------
61
62        @Check(CheckType.EXPENSIVE)
63        public void checkUpdateGrammarConsistency(EtsiBnf bnf) {
64                if (!checkUpdatedGrammarConsistency)
65                        return;
66
67                CompositeNode compNode = NodeUtil.getRootNode(bnf);
68                XtextResourceSet set = new XtextResourceSet();
69                URI uri = compNode.getElement().eResource().getURI();
70                Iterable<AbstractNode> allNodes = NodeUtil.getAllContents(compNode);
71                if(!bnf.getType().equals("/delta"))
72                        return;
73               
74                Resource coreRes = null;
75                Resource updatedRes = null;
76                EList<Import> imports = bnf.getImportSection().getImports();
77
78                for(int j=0; j<imports.size(); j++) {
79                        if(imports.get(j).getGrammarType().equals("core")) {
80                                String packageUri = uri.trimSegments(1).toPlatformString(true);
81                                String fullUri = packageUri + "/" +imports.get(j).getImportURI();
82                                coreRes= set.getResource( URI.createPlatformResourceURI(fullUri, true), true);
83                        }
84                        if(imports.get(j).getGrammarType().equals("update")) {
85                                String packageUri = uri.trimSegments(1).toPlatformString(true);
86                                String fullUri = packageUri + "/" +imports.get(j).getImportURI();
87                                updatedRes= set.getResource( URI.createPlatformResourceURI(fullUri, true), true);
88                        }
89                }
90               
91                if( (coreRes==null) || (updatedRes==null))
92                        return;
93
94                XtextResource coreResource = null;
95                XtextResource updatedResource = null;
96
97                if(coreRes instanceof XtextResource)
98                        coreResource = (XtextResource) coreRes;
99                if(updatedRes instanceof XtextResource)
100                        updatedResource = (XtextResource) updatedRes;
101
102                /*
103                 * the idea: get the core grammar and the updated grammar
104                 * for each extension rule in the delta grammar,
105                 *              find the corresponding rule in the updated grammar and the core grammar
106                 *              if it doesn't exist in the updated grammar write the inconsistency
107                 *              if it exists, compare to the rule in the core grammar
108                 */
109                for(AbstractNode node: allNodes) {
110                        if(node.getElement() instanceof ExtRule) {
111                                checkForConsistency(node, coreResource, updatedResource, compNode);
112                        }
113                }
114        }
115       
116        private boolean checkForConsistency(AbstractNode node, XtextResource coreResource, XtextResource updatedResource, CompositeNode compNode) {
117                //updated grammar:
118                AbstractNode updatedRule = null;
119                AbstractNode coreRule = null;
120                Rule currentRule = null;
121                for(AbstractNode uNode : NodeUtil.getAllContents(updatedResource.getParseResult().getRootNode())) {
122                        if (uNode.getElement() instanceof Rule) {
123                                currentRule  = (Rule) uNode.getElement();
124                                if (currentRule.getName().equals(((ExtRule) node.getElement()).getName())) {
125                                        updatedRule = uNode;
126                                        break;
127                                }
128                        }
129                }
130               
131                if(updatedRule == null) {
132                        warning(EbnfJavaValidator.packageConsistencyCheckRuleMissingDescription, node.getElement(), 1);
133                        return false;
134                } else { //core grammar
135                        for(AbstractNode cNode : NodeUtil.getAllContents(coreResource.getParseResult().getRootNode())) {
136                                if(cNode.getElement() instanceof Rule)
137                                        if(((Rule) cNode.getElement()).getName().equals(((ExtRule) node.getElement()).getName())) {
138                                                coreRule = cNode;
139                                                break;
140                                        }
141                        }
142                       
143                        if(coreRule == null){
144                                warning(EbnfJavaValidator.packageConsistencyCheckCorrespondingRuleMissingDescription, node.getElement(), 1);
145                                return false;
146                        }
147                       
148                        if (compareRules(coreRule, updatedRule)) {
149                                return true;
150                        } else {
151                                warning(EbnfJavaValidator.packageConsistencyCheckRuleDifferentDescription, node.getElement(), 1);
152                                return false;
153                        }
154                       
155                }
156        }
157
158        // returns true, if the rules are equal
159        private boolean compareRules(AbstractNode cNode, AbstractNode uNode) {
160                EList<LeafNode> cLeaves = removeWS(cNode.getLeafNodes());
161                EList<LeafNode> uLeaves = removeWS(uNode.getLeafNodes());
162                if (cLeaves.size() != uLeaves.size())
163                        return false;
164               
165                for(int i=0; i < cLeaves.size(); i++) {
166                        if(!(cLeaves.get(i).serialize().equals(uLeaves.get(i).serialize())))
167                                return false;
168                       
169                }
170                return true;
171        }
172
173        private EList<LeafNode> removeWS(EList<LeafNode> leaves) {
174                for(int i=0; i < leaves.size(); i++) {
175                        if(!(leaves.get(i).getGrammarElement() instanceof org.eclipse.xtext.impl.TerminalRuleImpl))
176                                leaves.remove(i);
177                }
178                return leaves;
179        }
180       
181        // ----------------------------------------------------------------------------------------------------
182
183        @Check(CheckType.EXPENSIVE)
184        public void checkReferencedOnlyOnce(Rule rule) {
185                if (!checkReferencedOnlyOnce)
186                        return;
187
188                if (EbnfAnalysisUtils.isTokenRule(rule))
189                        return;
190
191                List<Rule> references = EbnfAnalysisUtils.findReferences(rule,
192                                resourceDescriptions);
193
194                if (references.size() == 1) {
195                        warning(EbnfJavaValidator.ruleReferencedOneDescription, 1,
196                                        EbnfJavaValidator.ruleReferencedOneDescription);
197                }
198        }
199
200        // ----------------------------------------------------------------------------------------------------
201
202        @Check(CheckType.EXPENSIVE)
203        public void checkPassthroughRule(Rule rule) {
204                if (!checkPassthroughRule)
205                        return;
206
207                List<Rule> references = EbnfAnalysisUtils.findReferences(rule,
208                                resourceDescriptions);
209
210                if (EbnfAnalysisUtils.isPassthroughRule(rule)) {
211                        if (references.size() == 0) {
212                                warning(
213                                                EbnfJavaValidator.unreferencedPassthroughRuleDescription,
214                                                1,
215                                                EbnfJavaValidator.unreferencedPassthroughRuleDescription);
216                        } else {
217                                warning(EbnfJavaValidator.passthroughRuleDescription, 1,
218                                                EbnfJavaValidator.passthroughRuleDescription);
219                        }
220                }
221        }
222
223        // ----------------------------------------------------------------------------------------------------
224
225        @Check(CheckType.EXPENSIVE)
226        public void checkUnusedRule(Rule rule) {
227                if (!checkUnusedRule)
228                        return;
229
230                List<Rule> references = EbnfAnalysisUtils.findReferences(rule,
231                                resourceDescriptions);
232
233                if ((references.size() == 0) && (rule.getRulenumber() != 1))
234                        warning(EbnfJavaValidator.unusedRuleDescription, 1,
235                                        EbnfJavaValidator.unusedRuleDescription);
236        }
237
238        // ----------------------------------------------------------------------------------------------------
239
240        private List<DefinitionList> collectDefinitionLists(CompositeNode o) {
241                List<DefinitionList> list = new ArrayList<DefinitionList>();
242
243                for (int i = 0; i < o.getChildren().size(); i++) {
244                        AbstractNode child = o.getChildren().get(i);
245                        if (child.getElement() instanceof DefinitionList) {
246                                list.add((DefinitionList) child.getElement());
247                        }
248
249                        if (child instanceof CompositeNode) {
250                                list.addAll(collectDefinitionLists((CompositeNode) child));
251                        }
252                }
253
254                return list;
255        }
256
257        // ----------------------------------------------------------------------------------------------------
258
259        @Check(CheckType.EXPENSIVE)
260        public void checkEqualAlternative(Rule rule) {
261                if (!checkEqualAlternative)
262                        return;
263
264                // TODO: is not per rule, but global!
265
266                // quadratic!
267                CompositeNode startNode = NodeUtil.getNodeAdapter(rule).getParserNode();
268
269                List<DefinitionList> definitionLists = collectDefinitionLists(startNode);
270
271                for (int k = 0; k < definitionLists.size(); k++) {
272
273                        EList<SingleDefinition> singleDefinitions = definitionLists.get(k)
274                                        .getSingleDefinition();
275                        for (int i = 0; i < singleDefinitions.size(); i++) {
276                                for (int j = 0; j < singleDefinitions.size(); j++) {
277                                        if (i == j)
278                                                continue;
279
280                                        SingleDefinition upper = singleDefinitions.get(i);
281                                        SingleDefinition lower = singleDefinitions.get(j);
282                                        CompositeNode upperNode = NodeUtil.getNodeAdapter(upper)
283                                                        .getParserNode();
284                                        CompositeNode lowerNode = NodeUtil.getNodeAdapter(lower)
285                                                        .getParserNode();
286
287                                        String upperString = upperNode.serialize().trim()
288                                                        .replaceAll("[ \t\n\r]", "");
289                                        String lowerString = lowerNode.serialize().trim()
290                                                        .replaceAll("[ \t\n\r]", "");
291
292                                        if (lowerString.equals(upperString))
293                                                warning(EbnfJavaValidator.equalAlternativeDescription,
294                                                                1,
295                                                                EbnfJavaValidator.equalAlternativeDescription);
296                                }
297                        }
298                }
299
300        }
301
302        // ----------------------------------------------------------------------------------------------------
303
304        @Check(CheckType.EXPENSIVE)
305        public void checkDuplicateRules(Rule rule) {
306                if (!checkDuplicateRules)
307                        return;
308
309                EtsiBnf etsiBnfNode = (EtsiBnf) rule.eContainer().eContainer();
310               
311                CompositeNode definitionList = NodeUtil.getNodeAdapter(rule.getDefinitionList()).getParserNode();
312               
313                String rightHandSideText = definitionList.serialize().trim()
314                                .replaceAll("[ \t\n\r]", "");
315
316                for (int i = 0; i < etsiBnfNode.getBnfEntry().size(); i++) {
317                        BnfEntry currentNode = etsiBnfNode.getBnfEntry().get(i);
318                        if (currentNode == null)
319                                continue;
320                        if (currentNode.getRule() == null)
321                                continue;
322                        if (currentNode.getRule() == rule)
323                                continue;
324
325                        Rule currentRule = currentNode.getRule();
326                        CompositeNode currentRuleDefinitionList = NodeUtil.getNodeAdapter(currentRule.getDefinitionList()).getParserNode();
327                        String currentRuleRightHandSideText = currentRuleDefinitionList.serialize().trim()
328                        .replaceAll("[ \t\n\r]", "");
329
330                        if (currentRuleRightHandSideText.equals(rightHandSideText)) {
331                                        String description = EbnfJavaValidator.duplicateRulesDescription
332                                                        + " with rule \""
333                                                        + currentRule.getName()
334                                                        + "\" (Line "
335                                                        + NodeUtil.getNodeAdapter(currentRule).getParserNode().getLine() + ")";
336                                        warning(description, 1, description);
337                                }
338                        }
339        }
340       
341        // ----------------------------------------------------------------------------------------------------
342       
343        @Check(CheckType.EXPENSIVE)
344        public void checkSubruleDuplicates(EtsiBnf bnf) {
345                if (!checkSubruleDuplicates)
346                        return;
347               
348                HashMap<String, DuplicateEntry> dupesMap = new HashMap<String, DuplicateEntry>();
349                Set<String> taggedEntries = new HashSet<String>();
350               
351                // build dupes map
352                for (int i=0; i < bnf.getBnfEntry().size(); i++) {
353                        BnfEntry currentBnfEntry = bnf.getBnfEntry().get(i);
354                        if ((currentBnfEntry.getRule() != null) && (currentBnfEntry.getRule().getDefinitionList() != null)) {
355                               
356                                CompositeNode ruleParserNode = NodeUtil.getNodeAdapter(currentBnfEntry.getRule().getDefinitionList()).getParserNode();
357                                String ruleText = ruleParserNode.serialize().trim();
358                                String processedRuleText = textSpacer(ruleText);
359                               
360                                String trimmedRuleText = processedRuleText.replaceAll("[\t\n\r]", " ").replaceAll("[ ]+", " ");
361                               
362                                String[] parts = trimmedRuleText.split(" ");
363                               
364                                for (int j=0; j <= parts.length; j++) {
365                                        for (int k=j; k <= parts.length; k++) {
366                                                if (isBalancedPairs(parts, j, k) && (k-j > 1)) {
367                                                        String balancedSubString = createString(parts, j, k);
368                                                        DuplicateEntry mapEntry = dupesMap.get(balancedSubString);
369                                                        if (mapEntry == null) {
370                                                                mapEntry = new DuplicateEntry();
371                                                                mapEntry.setSnippet(balancedSubString);
372                                                                mapEntry.addRule(currentBnfEntry.getRule());
373                                                                dupesMap.put(balancedSubString, mapEntry);
374                                                        } else {
375                                                                mapEntry.addRule(currentBnfEntry.getRule());
376                                                                dupesMap.put(balancedSubString, mapEntry);
377                                                                taggedEntries.add(balancedSubString);
378                                                        }
379                                                }
380                                        }
381                                }
382                        }
383                }
384               
385                // create warnings
386               
387                Iterator<String> it = taggedEntries.iterator();
388               
389                while (it.hasNext()) {
390                        String entry = it.next();
391                        DuplicateEntry dupeEntry = dupesMap.get(entry);
392                        if (dupeEntry.getRules().size() < 2)
393                                continue;
394                       
395                        String warningText = "";
396                        warningText += entry + " is duplicated in the following rules: ";
397                        for (int i=0; i < dupeEntry.getRules().size(); i++) {
398                                Rule rule = dupeEntry.getRules().get(i);
399                                CompositeNode parserNode = NodeUtil.getNodeAdapter(rule).getParserNode();
400
401                                if (rule.getRulenumber() > 0) {
402                                        String ruleNumber = Integer.toString(rule.getRulenumber()).replaceAll("[ \t\n\r]", "");
403                                        warningText += ruleNumber;
404                                }
405                                warningText += " (Line ";
406                                warningText += parserNode.getLine();
407                                warningText += ")";
408                               
409                                if (i+1 < dupeEntry.getRules().size())
410                                        warningText += ", ";
411
412                        }
413
414                        for (int i=0; i < dupeEntry.getRules().size(); i++) {
415                                Rule rule = dupeEntry.getRules().get(i);
416                                CompositeNode parserNode = NodeUtil.getNodeAdapter(rule).getParserNode();
417                                warning(warningText, parserNode.getElement(), 1);
418                        }
419                }
420               
421        }
422
423        private String textSpacer(String ruleText) {
424                ruleText = ruleText + " ";
425                String processedRuleText = ruleText.replaceAll("([^\"])\\(([^\"])", "$1 ( $2"); // ( case 1
426                processedRuleText = processedRuleText.replaceAll("\\(([^\"])", " ( $1"); // ( case 2
427                processedRuleText = processedRuleText.replaceAll("([^\"])\\(\"", "$1 ( \""); // ( case 3
428
429                processedRuleText = processedRuleText.replaceAll("([^\"])\\)([^\"])", "$1 ) $2"); // ) case 1
430                processedRuleText = processedRuleText.replaceAll("\\)([^\"])", " ) $1"); // ) case 2
431                processedRuleText = processedRuleText.replaceAll("\"\\)([^\"])", "\" ) $1"); // ) case 3
432               
433                processedRuleText = processedRuleText.replaceAll("([^\"])\\{([^\"])", "$1 { $2"); // { case 1
434                processedRuleText = processedRuleText.replaceAll("\\{([^\"])", " { $1"); // { case 2
435                processedRuleText = processedRuleText.replaceAll("([^\"])\\{\"", "$1 { \""); // { case 3
436               
437                processedRuleText = processedRuleText.replaceAll("([^\"])\\}([^\\+\"])", "$1 } $2"); // } case 1
438                processedRuleText = processedRuleText.replaceAll("\\}([^\\+\"])", " } $1"); // } case 2
439                processedRuleText = processedRuleText.replaceAll("\"\\}([^\\+\"])", "\" } $1"); // } case 3
440               
441                processedRuleText = processedRuleText.replaceAll("([^\"])\\}\\+([^\"])", "$1 }\\+ $2"); // }+ case 1
442                processedRuleText = processedRuleText.replaceAll("\\}\\+([^\"])", " }\\+ $1 "); // }+ case 2
443                processedRuleText = processedRuleText.replaceAll("\"\\}\\+([^\"])", "\" }\\+ $1 "); // }+ case 3
444               
445                processedRuleText = processedRuleText.replaceAll("([^\"])\\[([^\"])", "$1 [ $2"); // [ case 1
446                processedRuleText = processedRuleText.replaceAll("\\[([^\"])", " [ $1"); // [ case 2
447                processedRuleText = processedRuleText.replaceAll("([^\"])\\[\"", "$1 [ \""); // [ case 3
448
449                processedRuleText = processedRuleText.replaceAll("([^\"])\\]([^\"])", "$1 ] $2"); // ] case 1
450                processedRuleText = processedRuleText.replaceAll("\\]([^\"])", " ] $1"); // ] case 2
451                processedRuleText = processedRuleText.replaceAll("\"\\]([^\"])", "\" ] $1"); // ] case 3
452                return processedRuleText;
453        }
454       
455        private boolean isBalancedPairs(String[] parts, int start, int end) {
456                Stack<String> pairStack = new Stack<String>();
457
458                if (start == end)
459                        return false;
460               
461                if (parts[start].contains("|"))
462                        return false;
463
464                if (parts[start].contains("}"))
465                        return false;
466
467                if (parts[start].contains("}+"))
468                        return false;
469               
470                if (parts[start].contains("]"))
471                        return false;
472
473                if (parts[end-1].contains("|"))
474                        return false;
475               
476                for (int i=start; i < end; i++) {
477                        String currentPart = parts[i];
478                        if (currentPart.equals("(") || currentPart.equals("{") || currentPart.equals("[")) {
479                                pairStack.push(currentPart);
480                        }
481                       
482                        if (!pairStack.isEmpty()) {
483                                if (currentPart.equals(")") && pairStack.peek().equals("(")) {
484                                        pairStack.pop();
485                                } else if (currentPart.equals("}") && pairStack.peek().equals("{")) {
486                                        pairStack.pop();
487                                } else if (currentPart.equals("}+") && pairStack.peek().equals("{")) {
488                                        pairStack.pop();
489                                } else if (currentPart.equals("]") && pairStack.peek().equals("[")) {
490                                        pairStack.pop();
491                                }
492                        } else {
493                                if (currentPart.equals(")") || currentPart.equals("}") || currentPart.equals("}+") || currentPart.equals("]")) {
494                                        return false;
495                                }
496                        }
497                }
498               
499                if (pairStack.empty())
500                        return true;
501               
502                return false;
503               
504        }
505       
506        private String createString(String[] parts, int start, int end) {
507                StringBuffer result = new StringBuffer();
508               
509                for (int i=start; i < end; i++) {
510                        result.append(parts[i]);
511                        result.append(" ");
512                }
513               
514                return result.toString().trim();
515        }
516       
517}
Note: See TracBrowser for help on using the repository browser.