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' || wikiText.charAt(end) == '\u2029';
 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                     // stumbled over a new type of newline?
 452                     // Or matcher is out of sync with checks above
 453                     errors.add("Empty group: " + this.matcher.group() + " char: " + (int)wikiText.charAt(end));
 454                     assert false;
 455                     throw new RuntimeException("matcher not in sync with code, or new type of newline, errors :" + errors);
 456                 }
 457                 return this;
 458             }
 459
 460             end = wikiText.length();
 461             return this;
 462
 463         } finally {
 464             if (!errors.isEmpty()) {
 465                 System.err.println("Errors: " + errors + ", token=" + token());
 466             }
 467         }
 468
 469     }
 470
 471     public String token() {
 472         final String token = wikiText.substring(start, end);
 473         assert token.equals("\n") || !token.endsWith("\n") : "token='" + token + "'";
 474         return token;
 475     }
 476
 477     final static String[] patterns = { "\n", "{{", "}}", "[[", "]]", "[", "]", "|", "=", "<!--" };
 478     private int escapedFindEnd(final int start, final String toFind) {
 479         assert tokenStack.isEmpty();
 480
 481         final boolean insideFunction = toFind.equals("}}");
 482
 483         int end = start;
 484         int firstNewline = -1;
 485         int[] nextMatch = new int[patterns.length];
 486         for (int i = 0; i < nextMatch.length; ++i) {
 487             nextMatch[i] = -2;
 488         }
 489         int singleBrackets = 0;
 490         while (end < wikiText.length()) {
 491             // Manual replacement for matcher.find(end),
 492             // because Java regexp is a ridiculously slow implementation.
 493             // Initialize to always match the end.
 494             int matchIdx = 0;
 495             for (int i = 0; i < nextMatch.length; ++i) {
 496                 if (nextMatch[i] <= end) {
 497                     nextMatch[i] = wikiText.indexOf(patterns[i], end);
 498                     if (nextMatch[i] == -1) nextMatch[i] = i > 0 ? 0x7fffffff : wikiText.length();
 499                 }
 500                 if (nextMatch[i] < nextMatch[matchIdx]) {
 501                     matchIdx = i;
 502                 }
 503             }
 504
 505             int matchStart = nextMatch[matchIdx];
 506             String matchText = patterns[matchIdx];
 507             int matchEnd = matchStart + matchText.length();
 508             if (matchIdx == 0) {
 509                 matchText = "";
 510                 matchEnd = matchStart;
 511             }
 512
 513             assert matchEnd > end || matchText.length() == 0: "Group=" + matchText;
 514             if (matchText.length() == 0) {
 515                 assert matchStart == wikiText.length() || wikiText.charAt(matchStart) == '\n' : wikiText + ", " + matchStart;
 516                 if (firstNewline == -1) {
 517                     firstNewline = matchEnd;
 518                 }
 519                 if (tokenStack.isEmpty() && toFind.equals("\n")) {
 520                     return matchStart;
 521                 }
 522                 ++end;
 523             } else if (tokenStack.isEmpty() && matchText.equals(toFind)) {
 524                 // The normal return....
 525                 if (insideFunction) {
 526                     addFunctionArg(insideFunction, matchStart);
 527                 }
 528                 return matchEnd;
 529             } else if (matchText.equals("[")) {
 530                 singleBrackets++;
 531             } else if (matchText.equals("]")) {
 532                 if (singleBrackets > 0) singleBrackets--;
 533             } else if (matchText.equals("[[") || matchText.equals("{{")) {
 534                 tokenStack.add(matchText);
 535             } else if (matchText.equals("]]") || matchText.equals("}}")) {
 536                 if (tokenStack.size() > 0) {
 537                     final String removed = tokenStack.remove(tokenStack.size() - 1);
 538                     if (removed.equals("{{") && !matchText.equals("}}")) {
 539                         if (singleBrackets >= 2) { // assume this is really two closing single ]
 540                             singleBrackets -= 2;
 541                             tokenStack.add(removed);
 542                         } else {
 543                             errors.add("Unmatched {{ error: " + wikiText.substring(start, matchEnd));
 544                             return safeIndexOf(wikiText, start, "\n", "\n");
 545                         }
 546                     } else if (removed.equals("[[") && !matchText.equals("]]")) {
 547                         errors.add("Unmatched [[ error: " + wikiText.substring(start, matchEnd));
 548                         return safeIndexOf(wikiText, start, "\n", "\n");
 549                     }
 550                 } else {
 551                     errors.add("Pop too many " + matchText + " error: " + wikiText.substring(start, matchEnd).replace("\n", "\\\\n"));
 552                     // If we were looking for a newline
 553                     return safeIndexOf(wikiText, start, "\n", "\n");
 554                 }
 555             } else if (matchText.equals("|")) {
 556                 if (tokenStack.isEmpty()) {
 557                     addFunctionArg(insideFunction, matchStart);
 558                 }
 559             } else if (matchText.equals("=")) {
 560                 if (tokenStack.isEmpty()) {
 561                     lastUnescapedEqualsPos = matchStart;
 562                 }
 563                 // Do nothing.  These can match spuriously, and if it's not the thing
 564                 // we're looking for, keep on going.
 565             } else if (matchText.equals("<!--")) {
 566                 end = wikiText.indexOf("-->", matchStart);
 567                 if (end == -1) {
 568                     errors.add("Unmatched <!-- error: " + wikiText.substring(start));
 569                     return safeIndexOf(wikiText, start, "\n", "\n");
 570                 }
 571             } else if (matchText.equals("''") || (matchText.startsWith("<") && matchText.endsWith(">"))) {
 572                 // Don't care.
 573             } else {
 574                 assert false : "Match text='" + matchText + "'";
 575                 throw new IllegalStateException();
 576             }
 577
 578             // Inside the while loop.  Just go forward.
 579             end = Math.max(end, matchEnd);
 580         }
 581         if (toFind.equals("\n") && tokenStack.isEmpty()) {
 582             // We were looking for the end, we got it.
 583             return end;
 584         }
 585         errors.add("Couldn't find: " + (toFind.equals("\n") ? "newline" : toFind) + ", "+ wikiText.substring(start));
 586         if (firstNewline != -1) {
 587             return firstNewline;
 588         }
 589         return end;
 590     }
 591
 592     private void addFunctionArg(final boolean insideFunction, final int matchStart) {
 593         if (firstUnescapedPipePos == -1) {
 594             firstUnescapedPipePos = lastUnescapedPipePos = matchStart;
 595         } else if (insideFunction) {
 596             if (lastUnescapedEqualsPos > lastUnescapedPipePos) {
 597                 final String key = wikiText.substring(lastUnescapedPipePos + 1, lastUnescapedEqualsPos);
 598                 final String value = wikiText.substring(lastUnescapedEqualsPos + 1, matchStart);
 599                 namedArgs.put(trimNewlines(key), trimNewlines(value));
 600             } else {
 601                 final String value = wikiText.substring(lastUnescapedPipePos + 1, matchStart);
 602                 positionArgs.add(trimNewlines(value));
 603             }
 604         }
 605         lastUnescapedPipePos = matchStart;
 606     }
 607
 608     static final String trimNewlines(String s) {
 609         while (s.startsWith("\n")) {
 610             s = s.substring(1);
 611         }
 612         while (s.endsWith("\n")) {
 613             s = s.substring(0, s.length() - 1);
 614         }
 615         return s.replace('\n', ' ');
 616     }
 617
 618     static int safeIndexOf(final String s, final int start, final String target, final String backup) {
 619         int close = s.indexOf(target, start);
 620         if (close != -1) {
 621             // Don't step over a \n.
 622             return close + (target.equals("\n") ? 0 : target.length());
 623         }
 624         close = s.indexOf(backup, start);
 625         if (close != -1) {
 626             return close + (backup.equals("\n") ? 0 : backup.length());
 627         }
 628         return s.length();
 629     }
 630
 631     public static String toPlainText(final String wikiText) {
 632         final WikiTokenizer wikiTokenizer = new WikiTokenizer(wikiText);
 633         final StringBuilder builder = new StringBuilder();
 634         while (wikiTokenizer.nextToken() != null) {
 635             if (wikiTokenizer.isPlainText()) {
 636                 builder.append(wikiTokenizer.token());
 637             } else if (wikiTokenizer.isWikiLink()) {
 638                 builder.append(wikiTokenizer.wikiLinkText());
 639             } else if (wikiTokenizer.isNewline()) {
 640                 builder.append("\n");
 641             } else if (wikiTokenizer.isFunction()) {
 642                 builder.append(wikiTokenizer.token());
 643             }
 644         }
 645         return builder.toString();
 646     }
 647
 648     public static StringBuilder appendFunction(final StringBuilder builder, final String name, List<String> args,
 649             final Map<String, String> namedArgs) {
 650         builder.append(name);
 651         for (final String arg : args) {
 652             builder.append("|").append(arg);
 653         }
 654         for (final Map.Entry<String, String> entry : namedArgs.entrySet()) {
 655             builder.append("|").append(entry.getKey()).append("=").append(entry.getValue());
 656         }
 657         return builder;
 658     }
 659
 660 }