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

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