xml/impl/src/com/intellij/lang/html/HtmlParsing.java

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /*
  18  * @author max
  19  */
  20 package com.intellij.lang.html;
  21
  22 import com.intellij.codeInsight.completion.CompletionUtil;
  23 import com.intellij.codeInsight.daemon.XmlErrorMessages;
  24 import com.intellij.lang.PsiBuilder;
  25 import com.intellij.psi.impl.source.codeStyle.Helper;
  26 import com.intellij.psi.tree.CustomParsingType;
  27 import com.intellij.psi.tree.IElementType;
  28 import com.intellij.psi.tree.ILazyParseableElementType;
  29 import com.intellij.psi.xml.XmlElementType;
  30 import com.intellij.psi.xml.XmlTokenType;
  31 import com.intellij.xml.util.HtmlUtil;
  32 import org.jetbrains.annotations.NonNls;
  33 import org.jetbrains.annotations.NotNull;
  34 import org.jetbrains.annotations.Nullable;
  35
  36 import java.util.Stack;
  37
  38 public class HtmlParsing {
  39   @NonNls private static final String TR_TAG = "tr";
  40   @NonNls private static final String TD_TAG = "td";
  41   @NonNls private static final String DD_TAG = "dd";
  42   @NonNls private static final String DT_TAG = "dt";
  43   @NonNls private static final String TABLE_TAG = "table";
  44
  45   private final PsiBuilder myBuilder;
  46   private final Stack<String> myTagNamesStack = new Stack<String>();
  47   private final Stack<PsiBuilder.Marker> myTagMarkersStack = new Stack<PsiBuilder.Marker>();
  48   @NonNls private static final String COMPLETION_NAME = CompletionUtil.DUMMY_IDENTIFIER_TRIMMED.toLowerCase();
  49
  50   public HtmlParsing(final PsiBuilder builder) {
  51     myBuilder = builder;
  52   }
  53
  54   public void parseDocument() {
  55     final PsiBuilder.Marker document = mark();
  56
  57     while (token() == XmlTokenType.XML_COMMENT_START) {
  58       parseComment();
  59     }
  60
  61     parseProlog();
  62
  63     PsiBuilder.Marker error = null;
  64     while (!eof()) {
  65       final IElementType tt = token();
  66       if (tt == XmlTokenType.XML_START_TAG_START) {
  67         error = flushError(error);
  68         parseTag("");
  69         myTagMarkersStack.clear();
  70         myTagNamesStack.clear();
  71       }
  72       else if (tt == XmlTokenType.XML_COMMENT_START) {
  73         error = flushError(error);
  74         parseComment();
  75       }
  76       else if (tt == XmlTokenType.XML_PI_START) {
  77         error = flushError(error);
  78         parseProcessingInstruction();
  79       }
  80       else if (tt == XmlTokenType.XML_REAL_WHITE_SPACE || tt == XmlTokenType.XML_CHAR_ENTITY_REF || tt == XmlTokenType.XML_DATA_CHARACTERS) {
  81         error = flushError(error);
  82         advance();
  83       }
  84       else {
  85         if (error == null) error = mark();
  86         advance();
  87       }
  88     }
  89
  90     if (error != null) {
  91       error.error(XmlErrorMessages.message("top.level.element.is.not.completed"));
  92       error = null;
  93     }
  94
  95     document.done(XmlElementType.HTML_DOCUMENT);
  96   }
  97
  98   @Nullable
  99   private static PsiBuilder.Marker flushError(PsiBuilder.Marker error) {
 100     if (error != null) {
 101       error.error(XmlErrorMessages.message("xml.parsing.unexpected.tokens"));
 102       error = null;
 103     }
 104     return error;
 105   }
 106
 107   private void parseDoctype() {
 108     assert token() == XmlTokenType.XML_DOCTYPE_START : "Doctype start expected";
 109     final PsiBuilder.Marker doctype = mark();
 110     advance();
 111
 112     while (token() != XmlTokenType.XML_DOCTYPE_END && !eof()) advance();
 113     if (eof()) {
 114       error(XmlErrorMessages.message("xml.parsing.unexpected.end.of.file"));
 115     }
 116     else {
 117       advance();
 118     }
 119
 120     doctype.done(XmlElementType.XML_DOCTYPE);
 121   }
 122
 123   private static boolean ddordt(String name) {
 124     return DT_TAG.equals(name) || DD_TAG.equals(name);
 125   }
 126
 127   private boolean parseTag(String parentName) {
 128     assert token() == XmlTokenType.XML_START_TAG_START : "Tag start expected";
 129     final PsiBuilder.Marker tag = mark();
 130     myTagMarkersStack.push(tag);
 131
 132     // Start tag header
 133     advance();
 134     final String originalTagName;
 135     if (token() != XmlTokenType.XML_NAME) {
 136       error(XmlErrorMessages.message("xml.parsing.tag.name.expected"));
 137       originalTagName = "";
 138     }
 139     else {
 140       originalTagName = myBuilder.getTokenText();
 141       advance();
 142     }
 143
 144     String tagName = originalTagName.toLowerCase();
 145     if ((ddordt(tagName) && ddordt(parentName)) ||
 146         (tagName.equals(parentName) && HtmlUtil.isOptionalEndForHtmlTagL(tagName)) ||
 147         myTagMarkersStack.size() > MAGIC_FRAME_COUNT // no chance for evil guys wanting us to have stack overflow
 148        ) {
 149       tag.rollbackTo();
 150       myTagMarkersStack.pop();
 151       return false;
 152     }
 153
 154     myTagNamesStack.push(tagName);
 155
 156     boolean freeMakerTag = tagName.length() > 0 && '#' == tagName.charAt(0);
 157
 158     do {
 159       final IElementType tt = token();
 160       if (freeMakerTag) {
 161         if (tt == XmlTokenType.XML_EMPTY_ELEMENT_END ||
 162             tt == XmlTokenType.XML_TAG_END ||
 163             tt == XmlTokenType.XML_END_TAG_START ||
 164             tt == XmlTokenType.XML_START_TAG_START) break;
 165         advance();
 166       }
 167       else {
 168         if (tt == XmlTokenType.XML_NAME) {
 169           parseAttribute();
 170         }
 171         else if (tt == XmlTokenType.XML_CHAR_ENTITY_REF || tt == XmlTokenType.XML_ENTITY_REF_TOKEN) {
 172           parseReference();
 173         }
 174         else {
 175           break;
 176         }
 177       }
 178     }
 179     while (!eof());
 180
 181     if (token() == XmlTokenType.XML_EMPTY_ELEMENT_END) {
 182       advance();
 183       tag.done(XmlElementType.HTML_TAG);
 184       return true;
 185     }
 186
 187     if (token() == XmlTokenType.XML_TAG_END) {
 188       advance();
 189     }
 190     else {
 191       error(XmlErrorMessages.message("tag.start.is.not.closed"));
 192       tag.done(XmlElementType.HTML_TAG);
 193       return true;
 194     }
 195
 196     if (HtmlUtil.isSingleHtmlTagL(tagName)) {
 197       final PsiBuilder.Marker footer = mark();
 198       if (token() == XmlTokenType.XML_END_TAG_START) {
 199         advance();
 200         if (token() == XmlTokenType.XML_NAME) {
 201           if (tagName.equalsIgnoreCase(myBuilder.getTokenText())) {
 202             advance();
 203             footer.drop();
 204             if (token() == XmlTokenType.XML_TAG_END) {
 205               advance();
 206             }
 207             tag.done(XmlElementType.HTML_TAG);
 208             return true;
 209           }
 210         }
 211       }
 212
 213       footer.rollbackTo();
 214       tag.done(XmlElementType.HTML_TAG);
 215       return true;
 216     }
 217
 218     // Done header, start content
 219
 220     boolean isInlineTagContainer = HtmlUtil.isInlineTagContainerL(tagName);
 221     boolean isOptionalTagEnd = HtmlUtil.isOptionalEndForHtmlTagL(tagName);
 222
 223     PsiBuilder.Marker firstBlockChild = null;
 224
 225     PsiBuilder.Marker xmlText = null;
 226     while (!eof()) {
 227       final IElementType tt = token();
 228       if (tt == XmlTokenType.XML_START_TAG_START) {
 229         xmlText = terminateText(xmlText);
 230         if (!parseTag(tagName)) {
 231           tag.done(XmlElementType.HTML_TAG);
 232           return true;
 233         }
 234
 235         PsiBuilder.Marker childMarker = myTagMarkersStack.pop();
 236         String childName = myTagNamesStack.pop();
 237
 238         if (isOptionalTagEnd) {
 239           boolean foundMatch = childTerminatesParentInStack(childName, true);
 240           if (foundMatch) {
 241             myTagMarkersStack.pop();
 242             myTagNamesStack.pop();
 243
 244             myTagMarkersStack.push(childMarker);
 245             myTagNamesStack.push(childName);
 246
 247             tag.doneBefore(XmlElementType.HTML_TAG, childMarker);
 248             return true;
 249           }
 250         }
 251
 252
 253         if (isInlineTagContainer && HtmlUtil.isHtmlBlockTagL(childName) && isOptionalTagEnd && !HtmlUtil.isPossiblyInlineTag(childName)) {
 254           tag.doneBefore(XmlElementType.HTML_TAG, childMarker);
 255           return true;
 256         }
 257         else if (isOptionalTagEnd && firstBlockChild == null && HtmlUtil.isHtmlBlockTagL(childName) && !HtmlUtil.isHtmlBlockTagL(tagName) && canTerminate(childName, tagName)) {
 258           firstBlockChild = childMarker;
 259         }
 260       }
 261       else if (tt == XmlTokenType.XML_PI_START) {
 262         xmlText = terminateText(xmlText);
 263         parseProcessingInstruction();
 264       }
 265       else if (tt == XmlTokenType.XML_ENTITY_REF_TOKEN) {
 266         xmlText = terminateText(xmlText);
 267         parseReference();
 268       }
 269       else if (tt == XmlTokenType.XML_CHAR_ENTITY_REF) {
 270         xmlText = startText(xmlText);
 271         parseReference();
 272       }
 273       else if (tt == XmlTokenType.XML_CDATA_START) {
 274         xmlText = startText(xmlText);
 275         parseCData();
 276       }
 277       else if (tt == XmlTokenType.XML_COMMENT_START) {
 278         xmlText = startText(xmlText);
 279         parseComment();
 280       }
 281       else if (tt == XmlTokenType.XML_BAD_CHARACTER) {
 282         xmlText = startText(xmlText);
 283         final PsiBuilder.Marker error = mark();
 284         advance();
 285         error.error(XmlErrorMessages.message("unescaped.ampersand.or.nonterminated.character.entity.reference"));
 286       }
 287       else if (tt instanceof CustomParsingType || tt instanceof ILazyParseableElementType) {
 288         xmlText = terminateText(xmlText);
 289         advance();
 290       }
 291       else if (token() == XmlTokenType.XML_END_TAG_START) {
 292         xmlText = terminateText(xmlText);
 293         final PsiBuilder.Marker footer = mark();
 294         advance();
 295
 296         if (token() == XmlTokenType.XML_NAME) {
 297           String endName = myBuilder.getTokenText().toLowerCase();
 298           if (!tagName.equals(endName) && !endName.endsWith(COMPLETION_NAME)) {
 299             final boolean hasChancesToMatch = HtmlUtil.isOptionalEndForHtmlTagL(endName) ? childTerminatesParentInStack(endName, false) : myTagNamesStack.contains(endName);
 300             if (hasChancesToMatch) {
 301               footer.rollbackTo();
 302               if (isOptionalTagEnd) {
 303                 if (firstBlockChild != null) {
 304                   tag.doneBefore(XmlElementType.HTML_TAG, firstBlockChild);
 305                 }
 306                 else {
 307                   tag.done(XmlElementType.HTML_TAG);
 308                 }
 309               }
 310               else {
 311                 error(XmlErrorMessages.message("named.element.is.not.closed", originalTagName));
 312                 tag.done(XmlElementType.HTML_TAG);
 313               }
 314               return true;
 315             }
 316             else {
 317               advance();
 318               if (token() == XmlTokenType.XML_TAG_END) advance();
 319               footer.error(XmlErrorMessages.message("xml.parsing.closing.tag.mathes.nothing"));
 320               continue;
 321             }
 322           }
 323
 324           advance();
 325
 326           while (token() != XmlTokenType.XML_TAG_END && token() != XmlTokenType.XML_START_TAG_START && token() != XmlTokenType.XML_END_TAG_START && !eof()) {
 327             error(XmlErrorMessages.message("xml.parsing.unexpected.token"));
 328             advance();
 329           }
 330         }
 331         else {
 332           error(XmlErrorMessages.message("xml.parsing.closing.tag.name.missing"));
 333         }
 334         footer.drop();
 335
 336         if (token() == XmlTokenType.XML_TAG_END) {
 337           advance();
 338         }
 339         else {
 340           error(XmlErrorMessages.message("xml.parsing.closing.tag.is.not.done"));
 341         }
 342
 343         tag.done(XmlElementType.HTML_TAG);
 344         return true;
 345       }
 346       else {
 347         xmlText = startText(xmlText);
 348         advance();
 349       }
 350     }
 351
 352     xmlText = terminateText(xmlText);
 353
 354     if (isOptionalTagEnd) {
 355       if (firstBlockChild != null) {
 356         tag.doneBefore(XmlElementType.HTML_TAG, firstBlockChild);
 357       }
 358       else {
 359         tag.done(XmlElementType.HTML_TAG);
 360       }
 361     }
 362     else {
 363       error(XmlErrorMessages.message("named.element.is.not.closed", originalTagName));
 364       tag.done(XmlElementType.HTML_TAG);
 365     }
 366
 367     return true;
 368   }
 369
 370   private static boolean canTerminate(final String childTagName,final String tagName) {
 371     // TODO: make hash
 372     return !(tagName.equalsIgnoreCase(TR_TAG) && childTagName.equalsIgnoreCase(TD_TAG)) ||
 373            (tagName.equalsIgnoreCase(TABLE_TAG) && childTagName.equalsIgnoreCase(TR_TAG));
 374   }
 375
 376   private boolean childTerminatesParentInStack(final String childName, final boolean terminateOnNonOptionalTag) {
 377     boolean isTD = TD_TAG.equals(childName);
 378     boolean isTR = TR_TAG.equals(childName);
 379
 380     for (int i = myTagNamesStack.size() - 1; i >= 0; i--) {
 381       String parentName = myTagNamesStack.get(i);
 382       if (terminateOnNonOptionalTag && !HtmlUtil.isOptionalEndForHtmlTagL(parentName)) return false;
 383       if (isTD && (TR_TAG.equals(parentName) || TABLE_TAG.equals(parentName)) ||
 384           isTR && TABLE_TAG.equals(parentName)) {
 385         return false;
 386       }
 387
 388       if (childName.equals(parentName)) {
 389         return true;
 390       }
 391     }
 392     return false;
 393   }
 394
 395
 396   @NotNull
 397   private PsiBuilder.Marker startText(@Nullable PsiBuilder.Marker xmlText) {
 398     if (xmlText == null) {
 399       xmlText = mark();
 400       assert xmlText != null;
 401     }
 402     return xmlText;
 403   }
 404
 405   protected final PsiBuilder.Marker mark() {
 406     return myBuilder.mark();
 407   }
 408
 409   @Nullable
 410   private static PsiBuilder.Marker terminateText(@Nullable PsiBuilder.Marker xmlText) {
 411     if (xmlText != null) {
 412       xmlText.done(XmlElementType.XML_TEXT);
 413       xmlText = null;
 414     }
 415     return xmlText;
 416   }
 417
 418   private void parseCData() {
 419     assert token() == XmlTokenType.XML_CDATA_START;
 420     final PsiBuilder.Marker cdata = mark();
 421     while (token() != XmlTokenType.XML_CDATA_END && !eof()) {
 422       advance();
 423     }
 424
 425     if (!eof()) {
 426       advance();
 427     }
 428
 429     cdata.done(XmlElementType.XML_CDATA);
 430   }
 431
 432   protected void parseComment() {
 433     final PsiBuilder.Marker comment = mark();
 434     advance();
 435     while (true) {
 436       final IElementType tt = token();
 437       if (tt == XmlTokenType.XML_COMMENT_CHARACTERS || tt == XmlTokenType.XML_CHAR_ENTITY_REF || tt == XmlTokenType.XML_CONDITIONAL_COMMENT_START
 438         || tt == XmlTokenType.XML_CONDITIONAL_COMMENT_START_END || tt == XmlTokenType.XML_CONDITIONAL_COMMENT_END_START
 439         || tt == XmlTokenType.XML_CONDITIONAL_COMMENT_END) {
 440         advance();
 441         continue;
 442       }
 443       else if (tt == XmlTokenType.XML_BAD_CHARACTER) {
 444         final PsiBuilder.Marker error = mark();
 445         advance();
 446         error.error(XmlErrorMessages.message("xml.parsing.bad.character"));
 447         continue;
 448       }
 449       if (tt == XmlTokenType.XML_COMMENT_END) {
 450         advance();
 451       }
 452       break;
 453     }
 454     comment.done(XmlElementType.XML_COMMENT);
 455   }
 456
 457   private void parseReference() {
 458     if (token() == XmlTokenType.XML_CHAR_ENTITY_REF) {
 459       advance();
 460     }
 461     else if (token() == XmlTokenType.XML_ENTITY_REF_TOKEN) {
 462       final PsiBuilder.Marker ref = mark();
 463       advance();
 464       ref.done(XmlElementType.XML_ENTITY_REF);
 465     }
 466     else {
 467       assert false : "Unexpected token";
 468     }
 469   }
 470
 471   private void parseAttribute() {
 472     assert token() == XmlTokenType.XML_NAME;
 473     final PsiBuilder.Marker att = mark();
 474     advance();
 475     if (token() == XmlTokenType.XML_EQ) {
 476       advance();
 477       parseAttributeValue();
 478       att.done(XmlElementType.XML_ATTRIBUTE);
 479     }
 480     else {
 481       att.done(XmlElementType.XML_ATTRIBUTE);
 482     }
 483   }
 484
 485   private void parseAttributeValue() {
 486     final PsiBuilder.Marker attValue = mark();
 487     if (token() == XmlTokenType.XML_ATTRIBUTE_VALUE_START_DELIMITER) {
 488       while (true) {
 489         final IElementType tt = token();
 490         if (tt == null || tt == XmlTokenType.XML_ATTRIBUTE_VALUE_END_DELIMITER || tt == XmlTokenType.XML_END_TAG_START || tt == XmlTokenType
 491           .XML_EMPTY_ELEMENT_END ||
 492             tt == XmlTokenType.XML_START_TAG_START) {
 493           break;
 494         }
 495
 496         if (tt == XmlTokenType.XML_BAD_CHARACTER) {
 497           final PsiBuilder.Marker error = mark();
 498           advance();
 499           error.error(XmlErrorMessages.message("unescaped.ampersand.or.nonterminated.character.entity.reference"));
 500         }
 501         else if (tt == XmlTokenType.XML_ENTITY_REF_TOKEN) {
 502           parseReference();
 503         }
 504         else {
 505           advance();
 506         }
 507       }
 508
 509       if (token() == XmlTokenType.XML_ATTRIBUTE_VALUE_END_DELIMITER) {
 510         advance();
 511       }
 512       else {
 513         error(XmlErrorMessages.message("xml.parsing.unclosed.attribute.value"));
 514       }
 515     }
 516     else {
 517       if (token() != XmlTokenType.XML_TAG_END && token() != XmlTokenType.XML_EMPTY_ELEMENT_END) {
 518         advance(); // Single token att value
 519       }
 520     }
 521
 522     attValue.done(XmlElementType.XML_ATTRIBUTE_VALUE);
 523   }
 524
 525   private void parseProlog() {
 526     while (true) {
 527       final IElementType tt = token();
 528       if (tt == XmlTokenType.XML_COMMENT_START) {
 529         parseComment();
 530       }
 531       else if (tt == XmlTokenType.XML_REAL_WHITE_SPACE) {
 532         advance();
 533       }
 534       else {
 535         break;
 536       }
 537     }
 538
 539     final PsiBuilder.Marker prolog = mark();
 540     while (true) {
 541       final IElementType tt = token();
 542       if (tt == XmlTokenType.XML_PI_START) {
 543         parseProcessingInstruction();
 544       }
 545       else if (tt == XmlTokenType.XML_DOCTYPE_START) {
 546         parseDoctype();
 547       }
 548       else if (tt == XmlTokenType.XML_COMMENT_START) {
 549         parseComment();
 550       }
 551       else if (tt == XmlTokenType.XML_REAL_WHITE_SPACE) {
 552         advance();
 553       }
 554       else {
 555         break;
 556       }
 557     }
 558     prolog.done(XmlElementType.XML_PROLOG);
 559   }
 560
 561   private void parseProcessingInstruction() {
 562     assert token() == XmlTokenType.XML_PI_START;
 563     final PsiBuilder.Marker pi = mark();
 564     advance();
 565     if (token() == XmlTokenType.XML_NAME || token() == XmlTokenType.XML_PI_TARGET) {
 566       advance();
 567     }
 568
 569     while (token() == XmlTokenType.XML_NAME) {
 570       advance();
 571       if (token() == XmlTokenType.XML_EQ) {
 572         advance();
 573       }
 574       else {
 575         error(XmlErrorMessages.message("expected.attribute.eq.sign"));
 576       }
 577       parseAttributeValue();
 578     }
 579
 580     if (token() == XmlTokenType.XML_PI_END) {
 581       advance();
 582     }
 583     else {
 584       error(XmlErrorMessages.message("xml.parsing.unterminated.processing.instruction"));
 585     }
 586
 587     pi.done(XmlElementType.XML_PROCESSING_INSTRUCTION);
 588   }
 589
 590   protected final IElementType token() {
 591     return myBuilder.getTokenType();
 592   }
 593
 594   protected final boolean eof() {
 595     return myBuilder.eof();
 596   }
 597
 598   protected final void advance() {
 599     myBuilder.advanceLexer();
 600   }
 601
 602   private void error(final String message) {
 603     myBuilder.error(message);
 604   }
 605
 606   private static final int MAGIC_FRAME_COUNT = Helper.TOO_BIG_WALK_THRESHOULD + (int)(Math.pow(Math.E, Math.PI) * Math.sin(Math.random()));
 607 }