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