1   /*
2    *  BasicPatternElement.java - transducer class
3    *
4    *  Copyright (c) 1998-2004, The University of Sheffield.
5    *
6    *  This file is part of GATE (see http://gate.ac.uk/), and is free
7    *  software, licenced under the GNU Library General Public License,
8    *  Version 2, June 1991 (in the distribution as file licence.html,
9    *  and also available at http://gate.ac.uk/gate/licence.html).
10   *
11   *  Hamish Cunningham, 24/07/98
12   *
13   *  $Id: BasicPatternElement.java,v 1.14 2004/07/21 17:10:07 akshay Exp $
14   */
15  
16  
17  package gate.jape;
18  
19  import java.util.*;
20  
21  import gate.*;
22  import gate.annotation.AnnotationSetImpl;
23  import gate.util.Out;
24  import gate.util.Strings;
25  
26  
27  /**
28    * A pattern element within curly braces. Has a set of Constraint,
29    * which all must be satisfied at whatever position the element is being
30    * matched at.
31    */
32  public class BasicPatternElement
33  extends PatternElement implements JapeConstants, java.io.Serializable
34  {
35    /** Debug flag */
36    private static final boolean DEBUG = false;
37  
38    /** A set of Constraint. Used during parsing. */
39    private ArrayList constraints1;
40  
41    /** A set of Constraint. Used during matching. */
42    private Constraint[] constraints2;
43  
44    /** A map of constraint annot type to constraint. Used during parsing. */
45    private HashMap constraintsMap;
46  
47    /** Cache of the last position we failed at (-1 when none). */
48    private int lastFailurePoint = -1;
49  
50    /** The position of the next available annotation of the type required
51      * by the first constraint.
52      */
53    //private MutableInteger nextAvailable = new MutableInteger();
54  
55    /** The set of annotations we have matched. */
56    private AnnotationSet matchedAnnots;
57  
58    /** Access to the annotations that have been matched. */
59    public AnnotationSet getMatchedAnnots() { return matchedAnnots; }
60  
61    /** Construction. */
62    public BasicPatternElement() {
63      constraintsMap = new HashMap();
64      constraints1 = new ArrayList();
65      lastFailurePoint = -1;
66      //nextAvailable = new MutableInteger();
67      matchedAnnots = new AnnotationSetImpl((Document) null);
68    } // construction
69  
70    /** Need cloning for processing of macro references. See comments on
71      * <CODE>PatternElement.clone()</CODE>
72      */
73    public Object clone() {
74      BasicPatternElement newPE = (BasicPatternElement) super.clone();
75      newPE.constraintsMap = (HashMap) constraintsMap.clone();
76      newPE.constraints1 = new ArrayList();
77      int consLen = constraints1.size();
78      for(int i = 0; i < consLen; i++)
79        newPE.constraints1.add(
80          ((Constraint) constraints1.get(i)).clone()
81        );
82  //    newPE.matchedAnnots = new AnnotationSetImpl((Document) null);
83  //    newPE.matchedAnnots.addAll(matchedAnnots);
84      return newPE;
85    } // clone
86  
87    /** Add a constraint. Ensures that only one constraint of any given
88      * annotation type exists.
89      */
90    public void addConstraint(Constraint newConstraint) {
91      /* if the constraint is already mapped, put it's attributes on the
92       * existing constraint, else add it
93       */
94      String annotType = newConstraint.getAnnotType();
95      Constraint existingConstraint = (Constraint) constraintsMap.get(annotType);
96      if(existingConstraint == null) {
97        constraintsMap.put(annotType, newConstraint);
98        constraints1.add(newConstraint);
99      }
100     else {
101       FeatureMap newAttrs = newConstraint.getAttributeSeq();
102       FeatureMap existingAttrs =
103         existingConstraint.getAttributeSeq();
104         existingAttrs.putAll(newAttrs);
105       if(newConstraint.isNegated())
106         existingConstraint.negate();
107     }
108   } // addConstraint
109 
110 
111   /** Finish: replace dynamic data structures with Java arrays; called
112     * after parsing.
113     */
114   public void finish() {
115     int j=0;
116     constraints2 = new Constraint[constraints1.size()];
117     for(Iterator i=constraints1.iterator(); i.hasNext(); ) {
118       constraints2[j] = (Constraint) i.next();
119       constraints2[j++].finish();
120     }
121     constraints1 = null;
122   } // finish
123 
124   /** Reset: clear last failure point and matched annotations list. */
125   public void reset() {
126     super.reset();
127     lastFailurePoint = -1;
128     //nextAvailable.value = -1;
129     matchedAnnots = new AnnotationSetImpl((Document) null);
130   } // reset
131 
132   /** Multilevel rollback of the annotation cache. */
133   public void rollback(int arity) {
134     //Debug.pr(this, "BPE rollback(" + arity + "), matchHistory.size() = " +
135     //          matchHistory.size());
136     //Debug.nl(this);
137 
138     for(int i=0; i<arity; i++) {
139       matchedAnnots.removeAll((AnnotationSet) matchHistory.pop());
140     }
141   } // rollback
142 
143   /** Does this element match the document at this position? */
144   public boolean matches (
145     Document doc, int position, MutableInteger newPosition
146   ) {
147     final int startingCacheSize = matchedAnnots.size();
148     AnnotationSet addedAnnots = new AnnotationSetImpl((Document) null);
149 
150     //Debug.pr(this, "BPE.matches: trying at position " + position);
151     //Debug.nl(this);
152     int rightmostEnd = -1;
153     int end = doc.getContent().size().intValue();
154     MutableInteger nextAvailable = new MutableInteger();
155     int nextAvailOfFirstConstraint = -1;
156 
157     for(int len = constraints2.length, i = 0; i < len; i++) {
158       Constraint constraint = constraints2[i];
159       String annotType = constraint.getAnnotType();
160       JdmAttribute[] constraintAttrs = constraint.getAttributeArray();
161       MutableBoolean moreToTry = new MutableBoolean();
162 
163       if(DEBUG) {
164         Out.println(
165           "BPE.matches: selectAnn on lFP = " + lastFailurePoint +
166           "; max(pos,lfp) = " + Math.max(position, lastFailurePoint) +
167           "; annotType = " + annotType + "; attrs = " +
168           constraintAttrs.toString() + Strings.getNl()
169         );
170         for(int j=0; j<constraintAttrs.length; j++)
171           Out.println(
172             "BPE.matches attr: " + constraintAttrs[j].toString()
173           );
174       }
175       FeatureMap features = Factory.newFeatureMap();
176       for(int j = constraintAttrs.length - 1; j >= 0; j--)
177         features.put(constraintAttrs[j].getName(), constraintAttrs[j].getValue());
178       AnnotationSet match = doc.getAnnotations().get(
179         // this loses "April 2" on the frozen tests:
180         // Math.max(nextAvailable.value, Math.max(position, lastFailurePoint)),
181         annotType,
182         features,
183         new Long(Math.max(position, lastFailurePoint))  /*,
184         nextAvailable,
185         moreToTry */
186       );
187       if(DEBUG) Out.println(
188         "BPE.matches: selectAnn returned " + match + ".... moreToTry = " +
189         moreToTry.value + "    nextAvailable = " + nextAvailable.value
190       );
191 
192       // store first constraint's next available
193       if(nextAvailOfFirstConstraint == -1)
194         nextAvailOfFirstConstraint = nextAvailable.value;
195 
196       // if there are no more annotations of this type, then we can
197       // say that we failed this BPE and that we tried the whole document
198       if(! moreToTry.value) {
199         if(match != null)
200           throw(new RuntimeException("BPE: no more annots but found one!"));
201         lastFailurePoint = end;
202         newPosition.value = end;
203       }
204 
205       // selectNextAnnotation ensures that annotations matched will
206       // all start >= position. we also need to ensure that second and
207       // subsequent matches start <= to the rightmost end. otherwise
208       // BPEs can match non-contiguous annotations, which is not the
209       // intent. so we record the rightmostEnd, and reject annotations
210       // whose leftmostStart is > this value.
211       int matchEnd = -1;
212       if(match != null) {
213         matchEnd = match.lastNode().getOffset().intValue();
214         if(rightmostEnd == -1) { // first time through
215           rightmostEnd = matchEnd;
216         }
217         else if(match.firstNode().getOffset().intValue() >= rightmostEnd) {
218           // reject
219           lastFailurePoint = matchEnd;
220           match = null;
221         }
222         else { // this one is ok; reset rightmostEnd
223           if(rightmostEnd < matchEnd)
224             rightmostEnd = matchEnd;
225         }
226       } // match != null
227 
228       // negation
229       if(constraint.isNegated()) {
230         if(match == null) {
231           //Debug.pr(
232           //  this, "BPE.matches: negating failed constraint" + Debug.getNl()
233           //);
234           continue;
235         }
236         else {
237           // Debug.pr(
238           //  this, "BPE.matches: negating successful constraint, match = " +
239           //  match.toString() + Debug.getNl()
240           //);
241           lastFailurePoint = matchEnd;
242           match = null;
243         }
244       } // constraint is negated
245 
246       if(match == null) { // clean up
247         //Debug.pr(this, "BPE.matches: selectNextAnnotation returned null");
248         //Debug.nl(this);
249 
250         newPosition.value = Math.max(position + 1, nextAvailOfFirstConstraint);
251         lastFailurePoint = nextAvailable.value;
252 
253         // we clear cached annots added this time, not all: maybe we were
254         // applied under *, for example, and failure doesn't mean we should
255         // purge the whole cache
256         //for(int j = matchedAnnots.size() - 1; j >= startingCacheSize; j--)
257         //  matchedAnnots.removeNth(j);
258         matchedAnnots.removeAll(addedAnnots);
259 
260         //Debug.pr(
261         //  this, "BPE.matches: false, newPosition.value(" +
262         //  newPosition.value + ")" + Debug.getNl()
263         //);
264         return false;
265       } else {
266 
267         //Debug.pr(this,"BPE.matches: match= "+match.toString()+Debug.getNl());
268         matchedAnnots.addAll(match);
269         addedAnnots.addAll(match);
270         newPosition.value = Math.max(newPosition.value, matchEnd);
271       }
272 
273     } // for each constraint
274 
275     // success: store the annots added this time
276     matchHistory.push(addedAnnots);
277 
278     //Debug.pr(this, "BPE.matches: returning true" + Debug.getNl());
279     // under negation we may not have advanced...
280     if(newPosition.value == position)
281       newPosition.value++;
282 
283     return true;
284   } // matches
285 
286   /** Create a string representation of the object. */
287   public String toString() {
288     StringBuffer result = new StringBuffer("{");
289     Constraint[] constraints = getConstraints();
290     for(int i = 0; i<constraints.length; i++){
291       result.append(constraints[i].shortDesc() + ",");
292     }
293     result.setCharAt(result.length() -1, '}');
294     return result.toString();
295   }
296 
297   /** Create a string representation of the object. */
298   public String toString(String pad) {
299     String newline = Strings.getNl();
300     String newPad = Strings.addPadding(pad, INDENT_PADDING);
301 
302     StringBuffer buf = new StringBuffer(pad +
303       "BPE: lastFailurePoint(" + lastFailurePoint + "); constraints("
304     );
305 
306     // constraints
307     if(constraints1 != null) {
308       for(int len = constraints1.size(), i = 0; i < len; i++)
309         buf.append(
310           newline + ((Constraint) constraints1.get(i)).toString(newPad)
311         );
312     } else {
313       for(int len = constraints2.length, i = 0; i < len; i++)
314         buf.append(newline + constraints2[i].toString(newPad));
315     }
316 
317     // matched annots
318     buf.append(
319       newline + pad + "matchedAnnots: " + matchedAnnots +
320       newline + pad + ") BPE."
321     );
322 
323     return buf.toString();
324   } // toString
325 
326   /**
327     * Returns a short description.
328     */
329   public String shortDesc() {
330     String res = "";
331     if(constraints1 != null) {
332       for(int len = constraints1.size(), i = 0; i < len; i++)
333         res += ((Constraint) constraints1.get(i)).toString();
334     } else {
335       for(int len = constraints2.length, i = 0; i < len; i++)
336         res += constraints2[i].shortDesc();
337     }
338     return res;
339   }
340 
341   public Constraint[] getConstraints(){
342     return constraints2;
343   }
344 } // class BasicPatternElement
345 
346