Clover icon

Coverage Report

  1. Project Clover database Thu Aug 13 2020 12:04:21 BST
  2. Package com.stevesoft.pat

File RegOpt.java

 

Coverage histogram

../../../img/srcFileCovDistChart7.png
27% of files have more coverage

Code metrics

96
186
14
3
450
368
82
0.44
13.29
4.67
5.86

Classes

Class Line # Actions
FastChar 15 3 5
1.0100%
Branch 39 98 38
0.6241610662.4%
RegOpt 271 85 39
0.741007274.1%
 

Contributing tests

This file is covered by 28 tests. .

Source view

1    //
2    // This software is now distributed according to
3    // the Lesser Gnu Public License. Please see
4    // http://www.gnu.org/copyleft/lesser.txt for
5    // the details.
6    // -- Happy Computing!
7    //
8    package com.stevesoft.pat;
9   
10    import java.util.Enumeration;
11    import java.util.Hashtable;
12    import java.util.Vector;
13   
14    /** This class is just like oneChar, but doesn't worry about case. */
 
15    class FastChar extends oneChar
16    {
 
17  946 toggle FastChar(char c)
18    {
19  946 super(c);
20    }
21   
 
22  159322 toggle public int matchInternal(int p, Pthings pt)
23    {
24  159322 return (p < pt.src.length() && pt.src.charAt(p) == c) ? nextMatch(
25    p + 1, pt) : -1;
26    }
27   
 
28  644 toggle Pattern clone1(Hashtable h)
29    {
30  644 return new FastChar(c);
31    }
32    }
33   
34    /**
35    * This class is a hashtable keyed by Character Objects. It is used to match
36    * things of the form (?:a..|b..|c..|..) match with greater efficiency -- by
37    * using a Hashtable that indexes into the group of patterns.
38    */
 
39    class Branch extends Pattern
40    {
41    Hashtable h = new Hashtable();
42   
43    // We need to keep track of the order
44    // of the keys -- if we don't then
45    // recompiling the output of toString
46    // may produce errors by re-ordering
47    // ()'s and changing the id number of
48    // the backreference associated with
49    // a subpattern.
50    Vector keys = new Vector();
51   
 
52  697 toggle Branch()
53    {
54    }
55   
 
56  161 toggle Pattern clone1(Hashtable x)
57    {
58  161 Branch b = new Branch();
59  161 b.keys = (Vector) keys.clone();
60  161 x.put(this, b);
61  161 x.put(b, b);
62   
63  483 for (int i = 0; i < keys.size(); i++)
64    {
65  322 Pattern p = (Pattern) h.get(keys.elementAt(i));
66  322 b.h.put(keys.elementAt(i), p.clone(x));
67    }
68  161 return b;
69    }
70   
71    // this function eliminates Branches with 0 or 1 elements.
 
72  86 toggle final Pattern reduce(boolean ignoreCase, boolean dontMinQ)
73    {
74  86 if (h.size() == 1)
75    {
76  0 Enumeration e = h.keys();
77  0 Character c = (Character) e.nextElement();
78  0 Pattern oc;
79  0 if (ignoreCase || dontMinQ)
80    {
81  0 oc = new oneChar(c.charValue());
82    }
83    else
84    {
85  0 oc = new FastChar(c.charValue());
86    }
87  0 oc.next = (Pattern) h.get(c);
88  0 oc.add(next);
89  0 return oc;
90    }
91  86 else if (h.size() == 0)
92    {
93  0 return null;
94    }
95  86 return this;
96    }
97   
 
98  170 toggle public patInt maxChars()
99    {
100  170 Enumeration e = h.keys();
101  170 patInt count = new patInt(0);
102  510 while (e.hasMoreElements())
103    {
104  340 Object key = e.nextElement();
105  340 Pattern pa = (Pattern) h.get(key);
106  340 patInt pi = pa.maxChars();
107  340 pi.inc();
108  340 count.maxeq(pi);
109    }
110  170 return count;
111    }
112   
 
113  170 toggle public patInt minChars()
114    {
115  170 Enumeration e = h.keys();
116  170 patInt count = new patInt(0);
117  510 while (e.hasMoreElements())
118    {
119  340 Object key = e.nextElement();
120  340 Pattern pa = (Pattern) h.get(key);
121  340 patInt pi = pa.minChars();
122  340 pi.inc();
123  340 count.mineq(pi);
124    }
125  170 return count;
126    }
127   
128    // adds a oneChar object to this Branch
 
129  180 toggle void addc(oneChar o, boolean ignoreCase, boolean dontMinQ)
130    {
131  180 Pattern n = o.next;
132  180 if (n == null)
133    {
134  168 n = new NullPattern();
135    }
136    else
137    {
138  12 n = RegOpt.opt(n, ignoreCase, dontMinQ);
139    }
140  180 n.setParent(this);
141  180 set(Character.valueOf(o.c), n, ignoreCase, dontMinQ);
142  180 if (ignoreCase)
143    {
144  0 if (o.c != o.altc)
145    {
146  0 set(Character.valueOf(o.altc), n, ignoreCase, dontMinQ);
147    }
148  0 if (o.c != o.altc2 && o.altc != o.altc2)
149    {
150  0 set(Character.valueOf(o.altc2), n, ignoreCase, dontMinQ);
151    }
152    }
153    }
154   
 
155  180 toggle void set(Character c, Pattern n, boolean igc, boolean dontMinQ)
156    {
157  180 Pattern p = (Pattern) h.get(c);
158  180 next = null;
159    // This letter is not yet used in the Branch object.
160    // We need to add it.
161  180 if (p == null)
162    {
163  172 if (n instanceof Or)
164    {
165    // A NullPattern is prepended to an Or
166    // to prevent confusing this object.
167    // For example: (boo|bug) => (b(?:oo|ug))
168    // during this process. However, we
169    // want (b(?:oo|ell)|bug)
170  4 NullPattern np = new NullPattern();
171  4 np.add(n);
172  4 h.put(c, np);
173    }
174    else
175    {
176  168 h.put(c, n);
177    }
178    // Make sure we remember the order things were
179    // added into the Branch object so that we can
180    // properly convert it to a String.
181  172 keys.addElement(c);
182    }
183  8 else if (p instanceof Or)
184    {
185  6 ((Or) p).addOr(n);
186    }
187  2 else if (p instanceof oneChar && n instanceof oneChar
188    && ((oneChar) p).c != ((oneChar) n).c)
189    {
190  0 Branch b = new Branch();
191  0 b.addc((oneChar) p, igc, dontMinQ);
192  0 b.addc((oneChar) n, igc, dontMinQ);
193  0 h.put(c, b);
194  0 b.setParent(this);
195    }
196  2 else if (p instanceof Branch && n instanceof oneChar)
197    {
198  0 ((Branch) p).addc((oneChar) n, igc, dontMinQ);
199  0 n.setParent(p);
200    }
201    else
202    {
203    // Create an Or object to receive the variety
204    // of branches in the pattern if the current letter
205    // is matched. We do not attempt to make these
206    // sub-branches into a Branch object yet.
207  2 Or o = new Or();
208  2 o.setParent(this);
209   
210    // Remove NullPattern from p -- it's no longer needed.
211  2 if (p instanceof NullPattern && p.parent == null && p.next != null)
212    {
213  2 o.addOr(p.next);
214    }
215    else
216    {
217  0 o.addOr(p);
218    }
219  2 o.addOr(n);
220   
221  2 Pattern optpat = RegOpt.opt(o, igc, dontMinQ);
222  2 h.put(c, optpat);
223  2 optpat.setParent(this);
224    }
225    }
226   
 
227  0 toggle public String toString()
228    {
229  0 StringBuffer sb = new StringBuffer();
230    // should protect this...
231  0 sb.append("(?:(?#branch)"); // Hashtable)");
232  0 for (int i = 0; i < keys.size(); i++)
233    {
234  0 Character c = (Character) keys.elementAt(i);
235  0 sb.append(c);
236  0 sb.append(h.get(c));
237  0 if (i + 1 < keys.size())
238    {
239  0 sb.append("|");
240    }
241    }
242  0 sb.append(")");
243  0 sb.append(nextString());
244  0 return sb.toString();
245    }
246   
 
247  315 toggle public int matchInternal(int pos, Pthings pt)
248    {
249  315 if (pos >= pt.src.length())
250    {
251  163 return -1;
252    }
253  152 Pattern n = (Pattern) h.get(Character.valueOf(pt.src.charAt(pos)));
254  152 if (n == null)
255    {
256  152 return -1;
257    }
258  0 if (pt.cbits != null && pt.cbits.get(pos))
259    {
260  0 return -1;
261    }
262  0 return n.matchInternal(pos + 1, pt);
263    }
264    }
265   
266    /**
267    * This is just a place to put the optimizing function. It is never instantiated
268    * as an Object. It just sorts through the RegOpt looking for things it can
269    * change and make faster.
270    */
 
271    public class RegOpt
272    {
 
273  2096 toggle static Pattern opt(Pattern p, boolean ignoreCase, boolean dontMinQ)
274    {
275  2096 if (p == null)
276    {
277  0 return p;
278    }
279  2096 if (p instanceof Bracket)
280    {
281  478 Bracket b = (Bracket) p;
282    // FastBracket is the only special
283    // optimized class to have its own
284    // source file.
285  478 p = FastBracket.process(b, ignoreCase);
286    // if(!(p instanceof FastBracket)
287    // p = Switch.process(b,ignoreCase);
288  478 p.next = b.next;
289  478 p.parent = b.parent;
290    }
291  1618 else if (p instanceof oneChar && !ignoreCase && !dontMinQ)
292    {
293  302 oneChar o = (oneChar) p;
294  302 p = new FastChar(o.c);
295  302 p.next = o.next;
296  302 p.parent = o.parent;
297    }
298  1316 else if (p instanceof Or && ((Or) p).leftForm().equals("(?:")
299    && ((Or) p).v.size() == 1)
300    { // Eliminate this Or Object.
301  0 Or o = (Or) p;
302  0 p = (Pattern) o.v.elementAt(0);
303  0 p.setParent(null);
304  0 p = RegOpt.opt(p, ignoreCase, dontMinQ);
305  0 p.add(o.next);
306    }
307  1316 else if (p instanceof Or)
308    {
309  536 Or o = (Or) p;
310  536 o.pv = null;
311  536 Vector v = o.v;
312  536 o.v = new Vector();
313  536 Branch b = new Branch();
314  536 b.parent = o.parent;
315  1176 for (int i = 0; i < v.size(); i++)
316    {
317  640 Pattern pp = (Pattern) v.elementAt(i);
318    // We want to have at least two oneChar's in
319    // the Or Object to consider making a Branch.
320  640 if (pp instanceof oneChar
321    && (b.h.size() >= 1 || (i + 1 < v.size() && v
322    .elementAt(i + 1) instanceof oneChar)))
323    {
324  180 b.addc((oneChar) pp, ignoreCase, dontMinQ);
325    }
326    else
327    {
328  460 if (b.keys.size() > 0)
329    {
330  0 Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
331  0 if (p2 != null)
332    {
333  0 o.addOr(p2);
334  0 b = new Branch();
335  0 b.parent = o.parent;
336    }
337    }
338  460 o.addOr(opt(pp, ignoreCase, dontMinQ));
339    }
340    }
341  536 if (b.keys.size() > 0)
342    {
343  86 Pattern p2 = (Pattern) b.reduce(ignoreCase, dontMinQ);
344  86 if (p2 != null)
345    {
346  86 o.addOr(p2);
347    }
348    }
349  536 if (o.v.size() == 1 && o.leftForm().equals("(?:"))
350    { // Eliminate Or Object
351  2 p = (Pattern) o.v.elementAt(0);
352  2 p.setParent(null);
353  2 p = RegOpt.opt(p, ignoreCase, dontMinQ);
354  2 p.add(o.next);
355    }
356    }
357  780 else if (p instanceof FastMulti)
358    {
359  560 PatternSub ps = (PatternSub) p;
360  560 ps.sub = RegOpt.opt(ps.sub, ignoreCase, dontMinQ);
361    }
362  220 else if (p instanceof Multi && safe4fm(((PatternSub) p).sub))
363    {
364  0 Multi m = (Multi) p;
365  0 FastMulti fm = null;
366  0 try
367    {
368  0 fm = new FastMulti(m.a, m.b, opt(m.sub, ignoreCase, dontMinQ));
369    } catch (RegSyntax rs)
370    {
371    }
372  0 fm.parent = m.parent;
373  0 fm.matchFewest = m.matchFewest;
374  0 fm.next = m.next;
375  0 p = fm;
376    }
377  2096 if (p.next != null)
378    {
379  764 p.next = opt(p.next, ignoreCase, dontMinQ);
380    }
381  2096 return p;
382    }
383   
 
384  2482 toggle final static boolean safe4fm(Pattern x)
385    {
386  5011 while (x != null)
387    {
388  2537 if (x instanceof Bracket)
389    {
390  2347 ;
391    }
392  190 else if (x instanceof Range)
393    {
394  101 ;
395    }
396  89 else if (x instanceof oneChar)
397    {
398  70 ;
399    }
400  19 else if (x instanceof Any)
401    {
402  0 ;
403    }
404  19 else if (x instanceof Custom
405    && ((Custom) x).v instanceof UniValidator)
406    {
407  0 ;
408    }
409  19 else if (x instanceof Or)
410    {
411  19 Or o = (Or) x;
412  19 if (!o.leftForm().equals("(?:"))
413    {
414  8 return false;
415    }
416  11 patInt lo = o.countMinChars();
417  11 patInt hi = o.countMaxChars();
418  11 if (!lo.equals(hi))
419    {
420  0 return false;
421    }
422  22 for (int i = 0; i < o.v.size(); i++)
423    {
424  11 if (!safe4fm((Pattern) o.v.elementAt(i)))
425    {
426  0 return false;
427    }
428    }
429    }
430    else
431    {
432  0 return false;
433    }
434  2529 x = x.next;
435    }
436  2474 return true;
437    }
438    /*
439    * public static void setParents(Regex r) { setParents(r.thePattern,null); }
440    * static void setParents(Pattern p,Pattern x) { if(p instanceof PatternSub &&
441    * !(p instanceof FastMulti) && !(p instanceof DotMulti)) RegOpt.setParents(
442    * ((PatternSub)p).sub, p); else if(p instanceof Or && !(p instanceof
443    * Bracket)) { Or o = (Or)p; for(int i=0;i<o.v.size();i++)
444    * RegOpt.setParents((Pattern)o.v.elementAt(i),o); } else if(p instanceof
445    * Branch) { Branch b = (Branch)p; Enumeration e = b.h.keys();
446    * while(e.hasMoreElements()) { Object o = e.nextElement(); RegOpt.setParents(
447    * (Pattern)b.h.get(o), b); } } if(p.next == null) p.parent = x; else {
448    * p.parent = null; RegOpt.setParents(p.next,x); } }
449    */
450    }
  • Report generated by OpenClover v 4.4.1 on Thu Aug 13 2020 12:06:48 BST using coverage data from Thu Aug 13 2020 12:06:40 BST.
  • OpenClover is free and open-source software.