ContentModel


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  package org.netbeans.modules.xml.dtd.grammar;
21  
22  import java.util.*;
23  
24  /**
25   * Implementation of queriable DTD content models. It is a hungry
26   * automaton.
27   *
28   * @see ContentModelTest
29   *
30   * @author  Petr Kuzel
31   */
32  abstract class ContentModel {
33  
34      /**
35       * Create model by parsing its string representation "|,*?+()WS".
36       * Caller must filter out <code>ANY</code>, <code>EMPTY</code> and
37       * <code>(#PCDATA)</codE> content models.
38       */
39      public static final ContentModel parseContentModel(String   model) {
40  
41          if (model == null || model.length() == 0) throw new IllegalArgumentException  ();
42  
43          PushbackStringTokenizer tokens = 
44              new PushbackStringTokenizer(model, "|,*?+() \t\n", true);           // NOI18N
45          String   next = tokens.nextToken();            
46          if (next.charAt(0) != '(' ) throw new IllegalStateException  ();
47          return parseContentModel(tokens);
48      }
49  
50      private static ContentModel parseContentModel(PushbackStringTokenizer tokens) {
51  
52          ContentModel model = null;;
53          List models = new ArrayList(7);
54          char type = 'E';
55          char ch;            
56          String   next;
57  
58          do {
59  
60              next = tokens.nextToken();
61              ch = next.charAt(0);
62              if (ch == ' ' || ch == '\t' || ch == '\n') continue;
63              if (ch == '#') { // #PCDATA
64                  do {
65                      ch = tokens.nextToken().charAt(0);
66                  } while (ch == ' ' || ch == '\t' || ch == '\n');
67                  if (ch != '|') throw new IllegalStateException  ();
68                  continue; 
69              } else if (ch == '(') {
70                  models.add(parseContentModel(tokens));
71              } else if (ch == '|') {
72                  type = '|';
73              } else if (ch == ',') {
74                  type = ',';
75              } else if (ch == ')') {
76                  break;
77              } else {
78                  model = new Element(next);
79  
80                  // optional element multiplicity
81  
82                  do {
83                      next = tokens.nextToken();
84                      ch = next.charAt(0);
85                  } while (ch == ' ' || ch == '\t' || ch == '\n');
86                  if (ch == '+') {
87                      model = new MultiplicityGroup(model, 1, -1);
88                  } else if (ch == '?') {
89                      model = new MultiplicityGroup(model, 0, 1);
90                  } else if (ch == '*') {
91                      model = new MultiplicityGroup(model, 0, -1);
92                  } else if (ch == ')') {
93                      // do not pushback!
94                  } else {
95                      tokens.pushback(next);
96                  }
97                  models.add(model);
98              }
99  
100         } while (ch != ')');
101 
102         // create models
103 
104         if (type == '|') {
105             model = new Choice((ContentModel[])models.toArray(new ContentModel[0]));
106         } else if (type == ',') {
107             model = new Sequence((ContentModel[])models.toArray(new ContentModel[0]));
108         } else {
109             // note model contains last Element
110         }
111 
112         // determine optional group multiplicity
113 
114         do {
115             if (tokens.hasMoreTokens() == false) break;
116             next = tokens.nextToken();
117             ch = next.charAt(0);
118         } while (ch == ' ' || ch == '\t' || ch == '\n');
119 
120         if (ch == '?') {
121             model = new MultiplicityGroup(model, 0, 1);
122         } else if (ch == '*') {
123             model = new MultiplicityGroup(model, 0, -1);
124         } else if (ch == '+') {
125             model = new MultiplicityGroup(model, 1, -1);
126         } else {
127             tokens.pushback(next);
128         }
129 
130         if(model == null) {
131             //75881 fix - the XMLSchema.dtd file contains multiple nested sections e.g.
132             //<!ENTITY % attrDecls    '((%attribute;| %attributeGroup;)*,(%anyAttribute;)?)'>
133             if(models.size() == 1) {
134                 //there is just one model inside (the mentioned case)
135                 //so we can return it
136                 return (ContentModel)models.get(0);
137             }
138         }
139 
140         return model;
141     }
142 
143     /**
144      * @return enumeration&lt;String&gt; or null if document is not valid.
145      */
146     public final Enumeration whatCanFollow(Enumeration en) {
147         reset();
148         Food food = new Food(en);
149         if (eat(food)) {
150             return possibilities();
151         } else {
152             return null;
153         }                        
154     }
155 
156     /**
157      * Reinitializes the content model to initial state.
158      */
159     protected void reset() {
160     }
161 
162     /**
163      * Move the automaton to next state. It is may not be called
164      * twice without reset!
165      * @return true if accepted the food, false at root model indicate document error
166      */
167     protected abstract boolean eat(Food food);
168 
169     /**
170      * Enumerate all <b>FIRST</b>s at current state.
171      * It must not be called if <code>eat</code> returned <code>false</code>
172      * @return possible completion
173      */
174     protected abstract Enumeration possibilities();
175 
176     /**
177      * Does need the content model a reset because it is in final state?
178      * @return true if it is in final state
179      */
180     protected boolean terminated() {
181         return false;
182     }
183     
184     /**
185      * Is the content model in current state optional?
186      */
187     protected boolean isOptional() {
188         return false;
189     }
190 
191     // ~~~~~~~~~~~~~~~~~~~~~~ Implemenation ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
192 
193     /**
194      * Single element
195      */
196     private static class Element extends ContentModel {
197 
198         private final String   name;
199 
200         private boolean full = false;
201 
202         public Element (String   name) {
203             this.name = name;
204         }
205 
206         protected void reset() {
207             full = false;
208         }
209         
210         protected boolean eat(Food food) {
211             if (food.hasNext() == false) {
212                 return true;
213             } else {
214                 String   next = food.next();
215                 if (this.name.equals(next)) {                
216                     full = true;
217                     return true;
218                 } else {
219                     return false;
220                 }
221             }
222         }
223 
224         protected Enumeration possibilities() {
225             if (terminated() == false) {
226                 return org.openide.util.Enumerations.singleton (name);
227             } else {
228                 return org.openide.util.Enumerations.empty();
229             }
230         }
231 
232         protected boolean terminated() {
233             return full;
234         }
235                 
236         public String   toString() {
237             return "Element[" + name + "]";
238         }
239     }
240 
241     
242     /**
243      * Mandatory sequence of models.
244      */
245     private static class Sequence extends ContentModel {
246 
247         private ContentModel[] models;
248 
249         // index of current model to use <0, models.length>
250         private int current = 0;
251 
252         public Sequence(ContentModel[] models) {
253             this.models = models;
254         }
255 
256         /**
257          * Reset all models upto (inclusive) current one.
258          */
259         protected void reset() {            
260             for (int i = 0; i<models.length; i++) {
261                 models[i].reset();
262             }
263             current = 0;
264         }
265 
266         /**
267          * Feed all sequence models until is enough food.
268          */
269         protected boolean eat(Food food) {
270 
271             while (food.hasNext()) {
272                 
273                 if (current == models.length) return true;
274                 
275                 int store = food.mark();
276                 boolean accept = models[current].eat(food);
277                 boolean more = food.hasNext();
278                 boolean terminated = models[current].terminated();
279                 
280                 if (accept == false) {
281                     return false;
282                 } else if (more) {                    
283                     current++;
284                 } else if (terminated == false && store != food.mark()) {
285                     
286                     // last model is possibly partially full, it could disapprove
287                     // if more food was provided -> move all subsequent automatons
288                     // to have accurate possibilities()
289 
290                     int level = food.mark();
291                     for (int i = current + 1; i<models.length; i++) {
292                         food.reset(store);
293                         if (models[i].eat(food) == false) {
294                             models[i].reset();
295                             if (models[i].isOptional() == false) break;
296                         } else {
297                             if (store == food.mark()) {
298                                 // the automaton was unattracted
299                                 models[i].reset();
300                             }
301                         }
302                     }
303                     food.reset(level);
304                     assert food.hasNext() == false : "Food mark/reset invariant is broken!";
305                                         
306                 } else if (terminated) {
307                     // it accepted and is complete
308                     current++;                    
309                 }
310             }
311                                     
312             return true;
313         }
314 
315         protected boolean terminated() {
316             if (current == models.length) return true;
317             if (current < models.length - 1) return false;
318             // last model may be active
319             return models[current].terminated();
320         }
321 
322         protected boolean isOptional() {
323             for (int i = 0; i<models.length; i++) {
324                 if (models[i].isOptional() == false) return false;
325             }
326             return true;
327         }
328         
329         protected Enumeration possibilities() {
330             if (terminated() == false) {
331                 Enumeration en = org.openide.util.Enumerations.empty();
332                 for ( int i = current; i<models.length; i++) {
333                     ContentModel next = models[i];                    
334                     en = org.openide.util.Enumerations.concat (en, next.possibilities());
335                     if (next.isOptional() == false) break;
336                 }
337                 return en;
338             } else {
339                 return org.openide.util.Enumerations.empty();
340             }
341         }
342 
343         public String   toString() {
344             String   ret = "Sequence[";
345             for (int i = 0; i<models.length; i++) {
346                 ret += models[i].toString() + ", ";
347             }
348             return ret + " current=" + current + "]";
349         }
350     }
351         
352     /**
353      * This content model allows options :-(.
354      */
355     private static class MultiplicityGroup extends ContentModel {
356 
357         private final int min; // 0 or 1
358         private final int max; // -1 for infinity (we must always test for ==)
359         private final ContentModel peer;
360 
361         // current occurence count
362         private int current = 0;
363         
364         public MultiplicityGroup (ContentModel model, int min, int max) {
365             this.peer = model;
366             this.min = min;
367             this.max = max;
368             current = 0;
369         }
370 
371         protected void reset() {
372             current = 0;
373             peer.reset();
374         }
375 
376         protected boolean eat(Food food) {
377 
378             boolean accept = current == min;
379             while (food.hasNext()) {
380                 
381                 if (current == max) return true;
382                 
383                 int store = food.mark();                
384                 boolean accepted = peer.eat(food);                
385                 
386                 if (accepted == false) {
387                     food.reset(store);
388                     return accept;
389                 } else if (food.hasNext()) {
390                     if (++current >= max && max > -1) {
391                         return true;
392                     };
393                     peer.reset();
394                 } else if (peer.terminated()) {
395                     // no more food, do not increment current for unterminated
396                     current ++;
397                 }
398                 accept = true;
399             }
400             
401             return true;
402         }
403 
404         public Enumeration possibilities() {            
405             if (terminated() == false) {
406                 // we force peer reinitialization
407                 if (peer.terminated()) peer.reset();
408                 return peer.possibilities();
409             } else {
410                 return org.openide.util.Enumerations.empty();
411             }
412         }
413 
414         protected boolean terminated() {
415             if (current != max) return false;
416             return peer.terminated();
417         }
418 
419         protected boolean isOptional() {
420             if (min <= current) return true;
421             return peer.isOptional();
422         }
423         
424         public String   toString() {
425             return "MultiplicityGroup[peer=" + peer + ", min=" + min + ", max=" + max + ", current=" + current + "]";
426         }
427     }
428 
429     /**
430      * At least one sub-content model must eat.     
431      */
432     private static class Choice extends ContentModel {
433 
434         private ContentModel[] models;
435         private boolean modelsThatNotAcceptedAtLeastOne[];
436 
437         private boolean terminated = false;
438 
439         // index of current model to use <0, models.length>
440         private int current = 0;
441 
442         public Choice(ContentModel[] models) {
443             this.models = models;
444             modelsThatNotAcceptedAtLeastOne = new boolean[models.length];
445         }
446 
447 
448         /**
449          * Reset all models upto (inclusive) current one.
450          */
451         protected void reset() {
452             for (int i = 0; i<models.length; i++) {
453                 models[i].reset();
454                 modelsThatNotAcceptedAtLeastOne[i] = false;
455             }
456             current = 0;
457             terminated = false;
458         }
459 
460         /**
461          * Feed all choice models until is enough food.
462          * @return trua if at least one accepted
463          */
464         protected boolean eat(Food food) {
465 
466             boolean accepted = food.hasNext() == false;
467             int newFood = food.mark();
468             boolean acceptedAndHungry = food.hasNext() == false;
469 
470             while (food.hasNext()) {
471 
472                 if (current == models.length) break;
473 
474                 int store = food.mark();
475                 boolean accept = models[current].eat(food);
476                 
477                 if (accept) {                    
478                     accepted = true;
479                     if (store == food.mark()) {
480                         modelsThatNotAcceptedAtLeastOne[current] = true;
481                     }
482                     if (food.hasNext() == false) {
483                         acceptedAndHungry |= models[current].terminated() == false;
484                     }
485                     newFood = Math.max(newFood, food.mark());
486                 } else {
487                     modelsThatNotAcceptedAtLeastOne[current] = true;
488                 }
489                 current++;
490                 food.reset(store);
491             }
492             
493             food.reset(newFood);
494             terminated = acceptedAndHungry == false;
495             return accepted;
496         }
497 
498         protected boolean terminated() {
499             return terminated;
500         }
501 
502         protected boolean isOptional() { 
503             boolean optional = false;
504             for (int i = 0; i<models.length; i++) {
505                 if (models[i].isOptional()) {
506                     optional = true;
507                     break;
508                 }
509             }
510 //            System.err.println("  " + this + " optional=" + optional);
511             return optional;
512         }
513         
514         protected Enumeration possibilities() {
515             if (terminated() == false) {
516                 Enumeration en = org.openide.util.Enumerations.empty();
517                 for ( int i = 0; i<models.length; i++) {
518                     if (modelsThatNotAcceptedAtLeastOne[i]) continue;
519                     ContentModel next = models[i];                    
520                     en = org.openide.util.Enumerations.concat (en, next.possibilities());
521                 }
522                 return en;
523             } else {
524                 return org.openide.util.Enumerations.empty();
525             }
526         }
527 
528         public String   toString() {
529             String   ret = "Choice[";
530             for (int i = 0; i<models.length; i++) {
531                 ret += models[i].toString() + ", ";
532             }
533             return ret + " current=" + current + "]";
534         }
535     }
536 
537 
538     // ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Utility classes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
539     
540     
541     /**
542      * Feeding for content model automaton. It is a kind of lazy initialized
543      * stack with fast backtracking.
544      */
545     private static class Food {
546 
547         // stack emulator
548         private final List list = new LinkedList();
549         
550         // source of lazy stack initilization
551         private final Enumeration en;
552         
553         // current stack position
554         private int current;
555         
556         public Food (Enumeration en) {
557             this.en = en;
558             current = 0;
559         }
560 
561         /**
562          * @return current stack location
563          */
564         public int mark() {
565             return current;
566         }
567         
568         /**
569          * Set new current
570          */
571         public void reset(int pos) {
572             current = pos;
573         }
574         
575         /**
576          * Return next available element.
577          * Must not be called if <code>hasNext</code> returns <code>null</code>
578          */
579         public String   next() {
580             if (hasNext() == false) {
581                 throw new IllegalStateException  ();
582             } else {
583                 String   next  = (String  ) list.get(current);
584                 current++;
585                 return next;
586             }
587         }
588         
589         /** 
590          * @return true if it is assured that next is available. 
591          */
592         public boolean hasNext() {
593             if (list.size() > current) return true;
594             if (en.hasMoreElements()) {
595                 String   next = (String  ) en.nextElement();
596                 return list.add(next);                
597             } else {
598                 return false;
599             }
600         }
601     }
602     
603     /**
604      * Partial implementation of single-pushback tokenizer.
605      */
606     private static class PushbackStringTokenizer extends StringTokenizer {
607         
608         private String   pushback = null;
609         
610         public PushbackStringTokenizer(String   tokens, String   delim, boolean inc) {
611             super(tokens, delim, inc);
612         }
613         
614         public String   nextToken() {
615             String   next;
616             if (pushback != null) {
617                 next = pushback;
618                 pushback = null;
619             } else {
620                 next = super.nextToken();
621             }            
622             return next;
623         }
624         
625         public boolean hasMoreTokens() {
626             if (pushback != null) {
627                 return true;
628             } else {
629                 return super.hasMoreTokens();
630             }
631         }
632         
633         public void pushback(String   pushback) {
634             if (this.pushback != null) throw new IllegalStateException  ();
635             this.pushback = pushback;
636         }
637     }
638     
639 }
640
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags