    1   /* InterruptibleCharSequenceTest
    2    *
    3    * Created on Jun 27, 2007
    4    *
    5    * Copyright (C) 2007 Internet Archive.
    6    *
    7    * This file is part of the Heritrix web crawler (crawler.archive.org).
    8    *
    9    * Heritrix is free software; you can redistribute it and/or modify
    10   * it under the terms of the GNU Lesser Public License as published by
    11   * the Free Software Foundation; either version 2.1 of the License, or
    12   * any later version.
    13   *
    14   * Heritrix is distributed in the hope that it will be useful,
    15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
    16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    17   * GNU Lesser Public License for more details.
    18   *
    19   * You should have received a copy of the GNU Lesser Public License
    20   * along with Heritrix; if not, write to the Free Software
    21   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    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      // this regex takes many seconds to fail on the input
    37      // (~20 seconds on 2Ghz Athlon64 JDK 1.6)
    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          // warm up
    57          tryMatch(inputNormal,regex);
    58          tryMatch(inputWrapped,regex);
    59          // inputWrapped.counter=0;
    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              //System.out.println(inputWrapped.counter+" steps");
    77              //inputWrapped.counter=0;
    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 }