1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 package org.archive.util;
24
25 import java.util.concurrent.BlockingQueue;
26 import java.util.concurrent.LinkedBlockingQueue;
27 import java.util.regex.Pattern;
28
29 import junit.framework.TestCase;
30
31 /***
32 * Tests (and
33 * @author gojomo
34 */
35 public class InterruptibleCharSequenceTest extends TestCase {
36
37
38 public static String BACKTRACKER = "^(((((a+)*)*)*)*)*$";
39 public static String INPUT = "aaaaab";
40
41 /***
42 * Development-time benchmarking of InterruptibleCharSequence in
43 * regex use. (Rename 'xest' to 'test' if wanted as unit test,
44 * but never actually fails anything -- just measures.)
45 *
46 * For reference the regex "^(((((a+)*)*)*)*)*$" requires
47 * 239,286,636 charAt(s) to fail on "aaaaab", which takes
48 * around 20 seconds on a 2Ghz Athlon64(x2) with JDK 1.6.
49 * The runtime overhead of checking interrupt status in this
50 * extreme case is around 5% in my tests.
51 */
52 public void xestOverhead() {
53 String regex = BACKTRACKER;
54 String inputNormal = INPUT;
55 InterruptibleCharSequence inputWrapped = new InterruptibleCharSequence(inputNormal);
56
57 tryMatch(inputNormal,regex);
58 tryMatch(inputWrapped,regex);
59
60 int trials = 5;
61 long stringTally = 0;
62 long icsTally = 0;
63 for(int i = 1; i <= trials; i++) {
64 System.out.println("trial "+i+" of "+trials);
65 long start = System.currentTimeMillis();
66 System.out.print("String ");
67 tryMatch(inputNormal,regex);
68 long end = System.currentTimeMillis();
69 System.out.println(end-start);
70 stringTally += (end-start);
71 start = System.currentTimeMillis();
72 System.out.print("InterruptibleCharSequence ");
73 tryMatch(inputWrapped,regex);
74 end = System.currentTimeMillis();
75 System.out.println(end-start);
76
77
78 icsTally += (end-start);
79 }
80 System.out.println("InterruptibleCharSequence took "+((float)icsTally)/stringTally+" longer.");
81 }
82
83 public boolean tryMatch(CharSequence input, String regex) {
84 return Pattern.matches(regex,input);
85 }
86
87 public Thread tryMatchInThread(final CharSequence input, final String regex, final BlockingQueue<Object> atFinish) {
88 Thread t = new Thread() {
89 public void run() {
90 boolean result;
91 try {
92 result = tryMatch(input,regex);
93 } catch (Exception e) {
94 atFinish.offer(e);
95 return;
96 }
97 atFinish.offer(result);
98 }
99 };
100 t.start();
101 return t;
102 }
103
104 public void testNoninterruptible() throws InterruptedException {
105 BlockingQueue<Object> q = new LinkedBlockingQueue<Object>();
106 Thread t = tryMatchInThread(INPUT, BACKTRACKER, q);
107 Thread.sleep(1000);
108 t.interrupt();
109 Object result = q.take();
110 assertTrue("mismatch uncompleted",Boolean.FALSE.equals(result));
111 }
112
113 public void testInterruptibility() throws InterruptedException {
114 BlockingQueue<Object> q = new LinkedBlockingQueue<Object>();
115 Thread t = tryMatchInThread(new InterruptibleCharSequence(INPUT), BACKTRACKER, q);
116 Thread.sleep(1000);
117 t.interrupt();
118 Object result = q.take();
119 assertTrue("exception not thrown",result instanceof RuntimeException);
120 }
121 }