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, matchEnd));
 531                         return safeIndexOf(wikiText, start, "\n", "\n");
 532                     } else if (removed.equals("[[") && !matchText.equals("]]")) {
 533                         errors.add("Unmatched [[ error: " + wikiText.substring(start, matchEnd));
 534                         return safeIndexOf(wikiText, start, "\n", "\n");
 535                     }
 536                 } else {
 537                     errors.add("Pop too many " + matchText + " error: " + wikiText.substring(start, matchEnd).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("-->", matchStart);
 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 }