src/com/hughes/android/dictionary/parser/WikiTokenizer.java

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 package com.hughes.android.dictionary.parser;
  16
  17 import java.util.ArrayList;
  18 import java.util.LinkedHashMap;
  19 import java.util.List;
  20 import java.util.Map;
  21 import java.util.regex.Matcher;
  22 import java.util.regex.Pattern;
  23
  24 public final class WikiTokenizer {
  25
  26   public static interface Callback {
  27     void onPlainText(final String text);
  28     void onMarkup(WikiTokenizer wikiTokenizer);
  29     void onWikiLink(WikiTokenizer wikiTokenizer);
  30     void onNewline(WikiTokenizer wikiTokenizer);
  31     void onFunction(final WikiTokenizer tokenizer, String functionName, List<String> functionPositionArgs,
  32         Map<String, String> functionNamedArgs);
  33     void onHeading(WikiTokenizer wikiTokenizer);
  34     void onListItem(WikiTokenizer wikiTokenizer);
  35     void onComment(WikiTokenizer wikiTokenizer);
  36     void onHtml(WikiTokenizer wikiTokenizer);
  37   }
  38
  39   public static class DoNothingCallback implements Callback {
  40
  41     @Override
  42     public void onPlainText(String text) {
  43     }
  44
  45     @Override
  46     public void onMarkup(WikiTokenizer wikiTokenizer) {
  47     }
  48
  49     @Override
  50     public void onWikiLink(WikiTokenizer wikiTokenizer) {
  51     }
  52
  53     @Override
  54     public void onNewline(WikiTokenizer wikiTokenizer) {
  55     }
  56
  57     @Override
  58     public void onFunction(WikiTokenizer tokenizer, String functionName,
  59         List<String> functionPositionArgs, Map<String, String> functionNamedArgs) {
  60     }
  61
  62     @Override
  63     public void onHeading(WikiTokenizer wikiTokenizer) {
  64     }
  65
  66     @Override
  67     public void onListItem(WikiTokenizer wikiTokenizer) {
  68     }
  69
  70     @Override
  71     public void onComment(WikiTokenizer wikiTokenizer) {
  72     }
  73
  74     @Override
  75     public void onHtml(WikiTokenizer wikiTokenizer) {
  76     }
  77   }
  78
  79   //private static final Pattern wikiTokenEvent = Pattern.compile("($)", Pattern.MULTILINE);
  80   private static final Pattern wikiTokenEvent = Pattern.compile("(" +
  81                 "\\{\\{|\\}\\}|" +
  82                 "\\[\\[|\\]\\]|" +
  83                 "\\||" +  // Need the | because we might have to find unescaped pipes
  84         "=|" +  // Need the = because we might have to find unescaped =
  85                 "<!--|" +
  86                 "''|" +
  87         "<pre>|" +
  88         "<math>|" +
  89         "<ref>|" +
  90                 "$)", Pattern.MULTILINE);
  91   private static final String listChars = "*#:;";
  92
  93
  94   final String wikiText;
  95   final Matcher matcher;
  96
  97   boolean justReturnedNewline = true;
  98   int lastLineStart = 0;
  99   int end = 0;
 100   int start = -1;
 101
 102   final List<String> errors = new ArrayList<String>();
 103   final List<String> tokenStack = new ArrayList<String>();
 104
 105
 106   private String headingWikiText;
 107   private int headingDepth;
 108   private int listPrefixEnd;
 109   private boolean isPlainText;
 110   private boolean isMarkup;
 111   private boolean isComment;
 112   private boolean isFunction;
 113   private boolean isWikiLink;
 114   private boolean isHtml;
 115   private int firstUnescapedPipePos;
 116
 117   private int lastUnescapedPipePos;
 118   private int lastUnescapedEqualsPos;
 119   private final List<String> positionArgs = new ArrayList<String>();
 120   private final Map<String,String> namedArgs = new LinkedHashMap<String,String>();
 121
 122
 123   public WikiTokenizer(final String wikiText) {
 124     this(wikiText, true);
 125   }
 126
 127   public WikiTokenizer(String wikiText, final boolean isNewline) {
 128     wikiText = wikiText.replace('\u2028', '\n');
 129     wikiText = wikiText.replace('\u0085', '\n');
 130     this.wikiText = wikiText;
 131     this.matcher = wikiTokenEvent.matcher(wikiText);
 132     justReturnedNewline = isNewline;
 133   }
 134
 135   private void clear() {
 136     errors.clear();
 137     tokenStack.clear();
 138
 139     headingWikiText = null;
 140     headingDepth = -1;
 141     listPrefixEnd = -1;
 142     isPlainText = false;
 143     isMarkup = false;
 144     isComment = false;
 145     isFunction = false;
 146     isWikiLink = false;
 147     isHtml = false;
 148
 149     firstUnescapedPipePos = -1;
 150     lastUnescapedPipePos = -1;
 151     lastUnescapedEqualsPos = -1;
 152     positionArgs.clear();
 153     namedArgs.clear();
 154   }
 155
 156   private static final Pattern POSSIBLE_WIKI_TEXT = Pattern.compile(
 157       "\\{\\{|" +
 158       "\\[\\[|" +
 159       "<!--|" +
 160       "''|" +
 161       "<pre>|" +
 162       "<math>|" +
 163       "<ref>|" +
 164       "[\n]"
 165       );
 166
 167   public static void dispatch(final String wikiText, final boolean isNewline, final Callback callback) {
 168     // Optimization...
 169     if (!POSSIBLE_WIKI_TEXT.matcher(wikiText).find()) {
 170       callback.onPlainText(wikiText);
 171     } else {
 172       final WikiTokenizer tokenizer = new WikiTokenizer(wikiText, isNewline);
 173       while (tokenizer.nextToken() != null) {
 174         if (tokenizer.isPlainText()) {
 175           callback.onPlainText(tokenizer.token());
 176         } else if (tokenizer.isMarkup()) {
 177           callback.onMarkup(tokenizer);
 178         } else if (tokenizer.isWikiLink()) {
 179           callback.onWikiLink(tokenizer);
 180         } else if (tokenizer.isNewline()) {
 181           callback.onNewline(tokenizer);
 182         } else if (tokenizer.isFunction()) {
 183           callback.onFunction(tokenizer, tokenizer.functionName(), tokenizer.functionPositionArgs(), tokenizer.functionNamedArgs());
 184         } else if (tokenizer.isHeading()) {
 185           callback.onHeading(tokenizer);
 186         } else if (tokenizer.isListItem()) {
 187           callback.onListItem(tokenizer);
 188         } else if (tokenizer.isComment()) {
 189           callback.onComment(tokenizer);
 190         } else if (tokenizer.isHtml()) {
 191           callback.onHtml(tokenizer);
 192         } else if (!tokenizer.errors.isEmpty()) {
 193           // Log was already printed....
 194         } else {
 195           throw new IllegalStateException("Unknown wiki state: " + tokenizer.token());
 196         }
 197       }
 198     }
 199   }
 200
 201   public List<String> errors() {
 202     return errors;
 203   }
 204
 205   public boolean isNewline() {
 206     return justReturnedNewline;
 207   }
 208
 209   public void returnToLineStart() {
 210     end = start = lastLineStart;
 211     justReturnedNewline = true;
 212   }
 213
 214   public boolean isHeading() {
 215     return headingWikiText != null;
 216   }
 217
 218   public String headingWikiText() {
 219     assert isHeading();
 220     return headingWikiText;
 221   }
 222
 223   public int headingDepth() {
 224     assert isHeading();
 225     return headingDepth;
 226   }
 227
 228   public boolean isMarkup() {
 229     return isMarkup;
 230   }
 231
 232   public boolean isComment() {
 233     return isComment;
 234   }
 235
 236   public boolean isListItem() {
 237     return listPrefixEnd != -1;
 238   }
 239
 240   public String listItemPrefix() {
 241     assert isListItem();
 242     return wikiText.substring(start, listPrefixEnd);
 243   }
 244
 245   public static String getListTag(char c) {
 246     if (c == '#') {
 247       return "ol";
 248     }
 249     return "ul";
 250   }
 251
 252   public String listItemWikiText() {
 253     assert isListItem();
 254     return wikiText.substring(listPrefixEnd, end);
 255   }
 256
 257   public boolean isFunction() {
 258     return isFunction;
 259   }
 260
 261   public String functionName() {
 262     assert isFunction();
 263     // "{{.."
 264     if (firstUnescapedPipePos != -1) {
 265       return trimNewlines(wikiText.substring(start + 2, firstUnescapedPipePos).trim());
 266     }
 267     final int safeEnd = Math.max(start + 2, end - 2);
 268     return trimNewlines(wikiText.substring(start + 2, safeEnd).trim());
 269   }
 270
 271   public List<String> functionPositionArgs() {
 272     return positionArgs;
 273   }
 274
 275   public Map<String, String> functionNamedArgs() {
 276     return namedArgs;
 277   }
 278
 279   public boolean isPlainText() {
 280     return isPlainText;
 281   }
 282
 283   public boolean isWikiLink() {
 284     return isWikiLink;
 285   }
 286
 287   public String wikiLinkText() {
 288     assert isWikiLink();
 289     // "[[.."
 290     if (lastUnescapedPipePos != -1) {
 291       return trimNewlines(wikiText.substring(lastUnescapedPipePos + 1, end - 2));
 292     }
 293     assert start + 2 < wikiText.length() && end >= 2: wikiText;
 294     return trimNewlines(wikiText.substring(start + 2, end - 2));
 295   }
 296
 297   public String wikiLinkDest() {
 298     assert isWikiLink();
 299     // "[[.."
 300     if (firstUnescapedPipePos != -1) {
 301       return trimNewlines(wikiText.substring(start + 2, firstUnescapedPipePos));
 302     }
 303     return null;
 304   }
 305
 306   public boolean isHtml() {
 307     return isHtml;
 308   }
 309
 310   public boolean remainderStartsWith(final String prefix) {
 311     return wikiText.startsWith(prefix, start);
 312   }
 313
 314   public void nextLine() {
 315     final int oldStart = start;
 316     while(nextToken() != null && !isNewline()) {}
 317     if (isNewline()) {
 318       --end;
 319     }
 320     start = oldStart;
 321   }
 322
 323
 324   public WikiTokenizer nextToken() {
 325     this.clear();
 326
 327     start = end;
 328
 329     if (justReturnedNewline) {
 330       lastLineStart = start;
 331     }
 332
 333     try {
 334
 335     final int len = wikiText.length();
 336     if (start >= len) {
 337       return null;
 338     }
 339
 340     // Eat a newline if we're looking at one:
 341     final boolean atNewline = wikiText.charAt(end) == '\n' || wikiText.charAt(end) == '\u2028';
 342     if (atNewline) {
 343       justReturnedNewline = true;
 344       ++end;
 345       return this;
 346     }
 347
 348     if (justReturnedNewline) {
 349       justReturnedNewline = false;
 350
 351       final char firstChar = wikiText.charAt(end);
 352       if (firstChar == '=') {
 353         final int headerStart = end;
 354         // Skip ===...
 355         while (++end < len && wikiText.charAt(end) == '=') {}
 356         final int headerTitleStart = end;
 357         headingDepth = headerTitleStart - headerStart;
 358         // Skip non-=...
 359         if (end < len) {
 360           final int nextNewline = safeIndexOf(wikiText, end, "\n", "\n");
 361           final int closingEquals = escapedFindEnd(end, "=");
 362           if (wikiText.charAt(closingEquals - 1) == '=') {
 363             end = closingEquals - 1;
 364           } else {
 365             end = nextNewline;
 366           }
 367         }
 368         final int headerTitleEnd = end;
 369         headingWikiText = wikiText.substring(headerTitleStart, headerTitleEnd);
 370         // Skip ===...
 371         while (end < len && ++end < len && wikiText.charAt(end) == '=') {}
 372         final int headerEnd = end;
 373         if (headerEnd - headerTitleEnd != headingDepth) {
 374           errors.add("Mismatched header depth: " + token());
 375         }
 376         return this;
 377       }
 378       if (listChars.indexOf(firstChar) != -1) {
 379         while (++end < len && listChars.indexOf(wikiText.charAt(end)) != -1) {}
 380         listPrefixEnd = end;
 381         end = escapedFindEnd(start, "\n");
 382         return this;
 383       }
 384     }
 385
 386     if (wikiText.startsWith("'''", start)) {
 387       isMarkup = true;
 388       end = start + 3;
 389       return this;
 390     }
 391
 392     if (wikiText.startsWith("''", start)) {
 393       isMarkup = true;
 394       end = start + 2;
 395       return this;
 396     }
 397
 398     if (wikiText.startsWith("[[", start)) {
 399       end = escapedFindEnd(start + 2, "]]");
 400       isWikiLink = errors.isEmpty();
 401       return this;
 402     }
 403
 404     if (wikiText.startsWith("{{", start)) {
 405       end = escapedFindEnd(start + 2, "}}");
 406       isFunction = errors.isEmpty();
 407       return this;
 408     }
 409
 410     if (wikiText.startsWith("<pre>", start)) {
 411       end = safeIndexOf(wikiText, start, "</pre>", "\n");
 412       isHtml = true;
 413       return this;
 414     }
 415
 416     if (wikiText.startsWith("<ref>", start)) {
 417         end = safeIndexOf(wikiText, start, "</ref>", "\n");
 418         isHtml = true;
 419         return this;
 420       }
 421
 422     if (wikiText.startsWith("<math>", start)) {
 423       end = safeIndexOf(wikiText, start, "</math>", "\n");
 424       isHtml = true;
 425       return this;
 426     }
 427
 428     if (wikiText.startsWith("<!--", start)) {
 429       isComment = true;
 430       end = safeIndexOf(wikiText, start, "-->", "\n");
 431       return this;
 432     }
 433
 434     if (wikiText.startsWith("}}", start) || wikiText.startsWith("]]", start)) {
 435       errors.add("Close without open!");
 436       end += 2;
 437       return this;
 438     }
 439
 440     if (wikiText.charAt(start) == '|' || wikiText.charAt(start) == '=') {
 441       isPlainText = true;
 442       ++end;
 443       return this;
 444     }
 445
 446
 447     if (this.matcher.find(start)) {
 448       end = this.matcher.start(1);
 449       isPlainText = true;
 450       if (end == start) {
 451         errors.add("Empty group: " + this.matcher.group());
 452         assert false;
 453       }
 454       return this;
 455     }
 456
 457     end = wikiText.length();
 458     return this;
 459
 460     } finally {
 461       if (!errors.isEmpty()) {
 462         System.err.println("Errors: " + errors + ", token=" + token());
 463       }
 464     }
 465
 466   }
 467
 468   public String token() {
 469     final String token = wikiText.substring(start, end);
 470     assert token.equals("\n") || !token.endsWith("\n") : "token='" + token + "'";
 471     return token;
 472   }
 473
 474   final static String[] patterns = { "\n", "{{", "}}", "[[", "]]", "|", "=", "<!--" };
 475   private int escapedFindEnd(final int start, final String toFind) {
 476     assert tokenStack.isEmpty();
 477
 478     final boolean insideFunction = toFind.equals("}}");
 479
 480     int end = start;
 481     int firstNewline = -1;
 482     int[] nextMatch = new int[8];
 483     for (int i = 0; i < 8; ++i) {
 484         nextMatch[i] = wikiText.indexOf(patterns[i], start);
 485         if (nextMatch[i] == -1) nextMatch[i] = i > 0 ? 0x7fffffff : wikiText.length();
 486     }
 487     while (end < wikiText.length()) {
 488         // Manual replacement for matcher.find(end),
 489         // because Java regexp is a ridiculously slow implementation.
 490         // Initialize to always match the end.
 491         int matchIdx = 0;
 492         for (int i = 1; i < 8; ++i) {
 493             if (nextMatch[i] < nextMatch[matchIdx]) {
 494                 matchIdx = i;
 495             }
 496         }
 497
 498         int matchStart = nextMatch[matchIdx];
 499         String matchText = patterns[matchIdx];
 500         int matchEnd = matchStart + matchText.length();
 501         nextMatch[matchIdx] = wikiText.indexOf(patterns[matchIdx], matchEnd);
 502         if (nextMatch[matchIdx] == -1) nextMatch[matchIdx] = matchIdx > 0 ? 0x7fffffff : wikiText.length();
 503         if (matchIdx == 0) {
 504             matchText = "";
 505             matchEnd = matchStart;
 506         }
 507
 508         assert matchEnd > end || matchText.length() == 0: "Group=" + matchText;
 509         if (matchText.length() == 0) {
 510           assert matchStart == wikiText.length() || wikiText.charAt(matchStart) == '\n' : wikiText + ", " + matchStart;
 511           if (firstNewline == -1) {
 512             firstNewline = matchEnd;
 513           }
 514           if (tokenStack.isEmpty() && toFind.equals("\n")) {
 515             return matchStart;
 516           }
 517           ++end;
 518         } else if (tokenStack.isEmpty() && matchText.equals(toFind)) {
 519           // The normal return....
 520           if (insideFunction) {
 521             addFunctionArg(insideFunction, matchStart);
 522           }
 523           return matchEnd;
 524         } else if (matchText.equals("[[") || matchText.equals("{{")) {
 525           tokenStack.add(matchText);
 526         } else if (matchText.equals("]]") || matchText.equals("}}")) {
 527           if (tokenStack.size() > 0) {
 528             final String removed = tokenStack.remove(tokenStack.size() - 1);
 529             if (removed.equals("{{") && !matchText.equals("}}")) {
 530               errors.add("Unmatched {{ error: " + wikiText.substring(start));
 531               return safeIndexOf(wikiText, start, "\n", "\n");
 532             } else if (removed.equals("[[") && !matchText.equals("]]")) {
 533               errors.add("Unmatched [[ error: " + wikiText.substring(start));
 534               return safeIndexOf(wikiText, start, "\n", "\n");
 535             }
 536           } else {
 537             errors.add("Pop too many error: " + wikiText.substring(start).replace("\n", "\\\\n"));
 538             // If we were looking for a newline
 539             return safeIndexOf(wikiText, start, "\n", "\n");
 540           }
 541         } else if (matchText.equals("|")) {
 542           if (tokenStack.isEmpty()) {
 543             addFunctionArg(insideFunction, matchStart);
 544           }
 545         } else if (matchText.equals("=")) {
 546           if (tokenStack.isEmpty()) {
 547             lastUnescapedEqualsPos = matchStart;
 548           }
 549           // Do nothing.  These can match spuriously, and if it's not the thing
 550           // we're looking for, keep on going.
 551         } else if (matchText.equals("<!--")) {
 552           end = wikiText.indexOf("-->");
 553           if (end == -1) {
 554             errors.add("Unmatched <!-- error: " + wikiText.substring(start));
 555             return safeIndexOf(wikiText, start, "\n", "\n");
 556           }
 557         } else if (matchText.equals("''") || (matchText.startsWith("<") && matchText.endsWith(">"))) {
 558           // Don't care.
 559         } else {
 560           assert false : "Match text='" + matchText + "'";
 561           throw new IllegalStateException();
 562         }
 563
 564       // Inside the while loop.  Just go forward.
 565       end = Math.max(end, matchEnd);
 566     }
 567     if (toFind.equals("\n") && tokenStack.isEmpty()) {
 568       // We were looking for the end, we got it.
 569       return end;
 570     }
 571     errors.add("Couldn't find: " + toFind + ", "+ wikiText.substring(start));
 572     if (firstNewline != -1) {
 573       return firstNewline;
 574     }
 575     return end;
 576   }
 577
 578   private void addFunctionArg(final boolean insideFunction, final int matchStart) {
 579     if (firstUnescapedPipePos == -1) {
 580       firstUnescapedPipePos = lastUnescapedPipePos = matchStart;
 581     } else if (insideFunction) {
 582       if (lastUnescapedEqualsPos > lastUnescapedPipePos) {
 583         final String key = wikiText.substring(lastUnescapedPipePos + 1, lastUnescapedEqualsPos);
 584         final String value = wikiText.substring(lastUnescapedEqualsPos + 1, matchStart);
 585         namedArgs.put(trimNewlines(key), trimNewlines(value));
 586       } else {
 587         final String value = wikiText.substring(lastUnescapedPipePos + 1, matchStart);
 588         positionArgs.add(trimNewlines(value));
 589       }
 590     }
 591     lastUnescapedPipePos = matchStart;
 592   }
 593
 594   static final String trimNewlines(String s) {
 595     while (s.startsWith("\n")) {
 596       s = s.substring(1);
 597     }
 598     while (s.endsWith("\n")) {
 599       s = s.substring(0, s.length() - 1);
 600     }
 601     return s.replace('\n', ' ');
 602   }
 603
 604   static int safeIndexOf(final String s, final int start, final String target, final String backup) {
 605     int close = s.indexOf(target, start);
 606     if (close != -1) {
 607       // Don't step over a \n.
 608       return close + (target.equals("\n") ? 0 : target.length());
 609     }
 610     close = s.indexOf(backup, start);
 611     if (close != -1) {
 612       return close + (backup.equals("\n") ? 0 : backup.length());
 613     }
 614     return s.length();
 615   }
 616
 617   public static String toPlainText(final String wikiText) {
 618     final WikiTokenizer wikiTokenizer = new WikiTokenizer(wikiText);
 619     final StringBuilder builder = new StringBuilder();
 620     while (wikiTokenizer.nextToken() != null) {
 621       if (wikiTokenizer.isPlainText()) {
 622         builder.append(wikiTokenizer.token());
 623       } else if (wikiTokenizer.isWikiLink()) {
 624         builder.append(wikiTokenizer.wikiLinkText());
 625       } else if (wikiTokenizer.isNewline()) {
 626         builder.append("\n");
 627       } else if (wikiTokenizer.isFunction()) {
 628         builder.append(wikiTokenizer.token());
 629       }
 630     }
 631     return builder.toString();
 632   }
 633
 634   public static StringBuilder appendFunction(final StringBuilder builder, final String name, List<String> args,
 635       final Map<String, String> namedArgs) {
 636     builder.append(name);
 637     for (final String arg : args) {
 638       builder.append("|").append(arg);
 639     }
 640     for (final Map.Entry<String, String> entry : namedArgs.entrySet()) {
 641       builder.append("|").append(entry.getKey()).append("=").append(entry.getValue());
 642     }
 643     return builder;
 644   }
 645
 646 }