WebCore/khtml/html/html_miscimpl.cpp

   1 /**
   2  * This file is part of the DOM implementation for KDE.
   3  *
   4  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
   5  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
   6  * Copyright (C) 2003 Apple Computer, Inc.
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public License
  19  * along with this library; see the file COPYING.LIB.  If not, write to
  20  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  21  * Boston, MA 02111-1307, USA.
  22  *
  23  */
  24 // -------------------------------------------------------------------------
  25 #include "html/html_miscimpl.h"
  26 #include "html/html_formimpl.h"
  27 #include "html/html_imageimpl.h"
  28 #include "html/html_documentimpl.h"
  29
  30 #include "misc/htmlhashes.h"
  31 #include "dom/dom_node.h"
  32
  33 using namespace DOM;
  34
  35 #include <kdebug.h>
  36
  37 HTMLBaseFontElementImpl::HTMLBaseFontElementImpl(DocumentPtr *doc)
  38     : HTMLElementImpl(doc)
  39 {
  40 }
  41
  42 HTMLBaseFontElementImpl::~HTMLBaseFontElementImpl()
  43 {
  44 }
  45
  46 NodeImpl::Id HTMLBaseFontElementImpl::id() const
  47 {
  48     return ID_BASEFONT;
  49 }
  50
  51 // -------------------------------------------------------------------------
  52
  53 HTMLCollectionImpl::HTMLCollectionImpl(NodeImpl *_base, int _type)
  54 {
  55     base = _base;
  56     base->ref();
  57     type = _type;
  58     idsDone = false;
  59     info = base->isDocumentNode() ? static_cast<HTMLDocumentImpl*>(base->getDocument())->collectionInfo(type) : 0;
  60 }
  61
  62 HTMLCollectionImpl::~HTMLCollectionImpl()
  63 {
  64     base->deref();
  65 }
  66
  67 HTMLCollectionImpl::CollectionInfo::CollectionInfo() :
  68     version(0)
  69 {
  70     idCache.setAutoDelete(true);
  71     nameCache.setAutoDelete(true);
  72     reset();
  73 }
  74
  75 void HTMLCollectionImpl::CollectionInfo::reset()
  76 {
  77     current = 0;
  78     position = 0;
  79     length = 0;
  80     haslength = false;
  81     elementsArrayPosition = 0;
  82     idCache.clear();
  83     nameCache.clear();
  84     hasNameCache = false;
  85 }
  86
  87 void HTMLCollectionImpl::resetCollectionInfo() const
  88 {
  89     unsigned int docversion = static_cast<HTMLDocumentImpl*>(base->getDocument())->domTreeVersion();
  90
  91     if (!info) {
  92         info = new CollectionInfo;
  93         info->version = docversion;
  94         return;
  95     }
  96
  97     if (info->version != docversion) {
  98         info->reset();
  99         info->version = docversion;
 100     }
 101 }
 102
 103
 104 NodeImpl *HTMLCollectionImpl::traverseNextItem(NodeImpl *current) const
 105 {
 106     current = current->traverseNextNode();
 107
 108     while (current) {
 109         if(current->nodeType() == Node::ELEMENT_NODE) {
 110             bool found = false;
 111             bool deep = true;
 112             HTMLElementImpl *e = static_cast<HTMLElementImpl *>(current);
 113             switch(type) {
 114             case DOC_IMAGES:
 115                 if(e->id() == ID_IMG)
 116                     found = true;
 117                 break;
 118             case DOC_FORMS:
 119                 if(e->id() == ID_FORM)
 120                     found = true;
 121                 break;
 122             case TABLE_TBODIES:
 123                 if(e->id() == ID_TBODY)
 124                     found = true;
 125                 else if(e->id() == ID_TABLE)
 126                     deep = false;
 127                 break;
 128             case TR_CELLS:
 129                 if(e->id() == ID_TD || e->id() == ID_TH)
 130                     found = true;
 131                 else if(e->id() == ID_TABLE)
 132                     deep = false;
 133                 break;
 134             case TABLE_ROWS:
 135             case TSECTION_ROWS:
 136                 if(e->id() == ID_TR)
 137                     found = true;
 138                 else if(e->id() == ID_TABLE)
 139                     deep = false;
 140                 break;
 141             case SELECT_OPTIONS:
 142                 if(e->id() == ID_OPTION)
 143                     found = true;
 144                 break;
 145             case MAP_AREAS:
 146                 if(e->id() == ID_AREA)
 147                     found = true;
 148                 break;
 149             case DOC_APPLETS:   // all OBJECT and APPLET elements
 150                 if(e->id() == ID_OBJECT || e->id() == ID_APPLET)
 151                     found = true;
 152                 break;
 153             case DOC_EMBEDS:   // all EMBED elements
 154                 if(e->id() == ID_EMBED)
 155                     found = true;
 156                 break;
 157             case DOC_LINKS:     // all A _and_ AREA elements with a value for href
 158                 if(e->id() == ID_A || e->id() == ID_AREA)
 159                     if(!e->getAttribute(ATTR_HREF).isNull())
 160                         found = true;
 161                 break;
 162             case DOC_ANCHORS:      // all A elements with a value for name or an id attribute
 163                 if(e->id() == ID_A)
 164                     if(!e->getAttribute(ATTR_NAME).isNull())
 165                         found = true;
 166                 break;
 167             case DOC_ALL:
 168                 found = true;
 169                 break;
 170             case NODE_CHILDREN:
 171                 found = true;
 172                 deep = false;
 173                 break;
 174             default:
 175                 kdDebug( 6030 ) << "Error in HTMLCollection, wrong tagId!" << endl;
 176             }
 177             if (found) {
 178                 return current;
 179             }
 180             if (deep) {
 181                 current = current->traverseNextNode(base);
 182                 continue;
 183             }
 184         }
 185         current = current->traverseNextSibling(base);
 186     }
 187     return 0;
 188 }
 189
 190
 191 unsigned long HTMLCollectionImpl::calcLength() const
 192 {
 193     unsigned long len = 0;
 194
 195     for (NodeImpl *current = traverseNextItem(base); current; current = traverseNextItem(current)) {
 196         len++;
 197     }
 198
 199     return len;
 200 }
 201
 202 // since the collections are to be "live", we have to do the
 203 // calculation every time if anything has changed
 204 unsigned long HTMLCollectionImpl::length() const
 205 {
 206     resetCollectionInfo();
 207     if (!info->haslength) {
 208         info->length = calcLength();
 209         info->haslength = true;
 210     }
 211     return info->length;
 212 }
 213
 214 NodeImpl *HTMLCollectionImpl::item( unsigned long index ) const
 215 {
 216      resetCollectionInfo();
 217      if (info->current && info->position == index) {
 218          return info->current;
 219      }
 220      if (info->haslength && info->length <= index) {
 221          return 0;
 222      }
 223      if (!info->current || info->position > index) {
 224          info->current = traverseNextItem(base);
 225          info->position = 0;
 226          if (!info->current)
 227              return 0;
 228      }
 229      NodeImpl *node = info->current;
 230      for (unsigned pos = info->position; pos < index; pos++) {
 231          node = traverseNextItem(node);
 232      }
 233      info->current = node;
 234      info->position = index;
 235      return info->current;
 236 }
 237
 238 NodeImpl *HTMLCollectionImpl::firstItem() const
 239 {
 240      return item(0);
 241 }
 242
 243 NodeImpl *HTMLCollectionImpl::nextItem() const
 244 {
 245      resetCollectionInfo();
 246
 247      // Look for the 'second' item. The first one is currentItem, already given back.
 248      NodeImpl *retval = traverseNextItem(info->current);
 249      info->current = retval;
 250      info->position++;
 251      return retval;
 252 }
 253
 254 bool HTMLCollectionImpl::checkForNameMatch(NodeImpl *node, bool checkName, const DOMString &name, bool caseSensitive) const
 255 {
 256     ElementImpl *e = static_cast<ElementImpl *>(node);
 257     if (caseSensitive) {
 258         if (checkName) {
 259             // document.all returns only images, forms, applets, objects and embeds
 260             // by name (though everything by id)
 261             if (type == DOC_ALL &&
 262                 !(e->id() == ID_IMG || e->id() == ID_FORM ||
 263                   e->id() == ID_APPLET || e->id() == ID_OBJECT ||
 264                   e->id() == ID_EMBED))
 265                 return false;
 266
 267             return e->getAttribute(ATTR_NAME) == name && e->getAttribute(ATTR_ID) != name;
 268         } else {
 269             return e->getAttribute(ATTR_ID) == name;
 270         }
 271     } else {
 272         if (checkName) {
 273             // document.all returns only images, forms, applets, objects and embeds
 274             // by name (though everything by id)
 275             if (type == DOC_ALL &&
 276                 !(e->id() == ID_IMG || e->id() == ID_FORM ||
 277                   e->id() == ID_APPLET || e->id() == ID_OBJECT ||
 278                   e->id() == ID_EMBED))
 279                 return false;
 280
 281             return e->getAttribute(ATTR_NAME).domString().lower() == name.lower() &&
 282                 e->getAttribute(ATTR_ID).domString().lower() != name.lower();
 283         } else {
 284             return e->getAttribute(ATTR_ID).domString().lower() == name.lower();
 285         }
 286     }
 287 }
 288
 289
 290 NodeImpl *HTMLCollectionImpl::namedItem( const DOMString &name, bool caseSensitive ) const
 291 {
 292     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
 293     // This method first searches for an object with a matching id
 294     // attribute. If a match is not found, the method then searches for an
 295     // object with a matching name attribute, but only on those elements
 296     // that are allowed a name attribute.
 297     resetCollectionInfo();
 298     idsDone = false;
 299
 300     NodeImpl *n;
 301     for (n = traverseNextItem(base); n; n = traverseNextItem(n)) {
 302         if (checkForNameMatch(n, idsDone, name, caseSensitive)) {
 303             break;
 304         }
 305     }
 306
 307     info->current = n;
 308     if(info->current)
 309         return info->current;
 310     idsDone = true;
 311
 312     for (n = traverseNextItem(base); n; n = traverseNextItem(n)) {
 313         if (checkForNameMatch(n, idsDone, name, caseSensitive)) {
 314             break;
 315         }
 316     }
 317
 318     info->current = n;
 319     return info->current;
 320 }
 321
 322 template<class T> static void appendToVector(QPtrVector<T> *vec, T *item)
 323 {
 324     unsigned size = vec->size();
 325     unsigned count = vec->count();
 326     if (size == count)
 327         vec->resize(size == 0 ? 8 : (int)(size * 1.5));
 328     vec->insert(count, item);
 329 }
 330
 331 void HTMLCollectionImpl::updateNameCache() const
 332 {
 333     if (info->hasNameCache)
 334         return;
 335
 336     for (NodeImpl *n = traverseNextItem(base); n; n = traverseNextItem(n)) {
 337         ElementImpl *e = static_cast<ElementImpl *>(n);
 338         QString idAttr = e->getAttribute(ATTR_ID).string();
 339         QString nameAttr = e->getAttribute(ATTR_NAME).string();
 340         if (!idAttr.isEmpty()) {
 341             // add to id cache
 342             QPtrVector<NodeImpl> *idVector = info->idCache.find(idAttr);
 343             if (!idVector) {
 344                 idVector = new QPtrVector<NodeImpl>;
 345                 info->idCache.insert(idAttr, idVector);
 346             }
 347             appendToVector(idVector, n);
 348         }
 349         if (!nameAttr.isEmpty() && idAttr != nameAttr
 350             && (type != DOC_ALL ||
 351                 (e->id() == ID_IMG || e->id() == ID_FORM ||
 352                  e->id() == ID_APPLET || e->id() == ID_OBJECT ||
 353                  e->id() == ID_EMBED))) {
 354             // add to name cache
 355             QPtrVector<NodeImpl> *nameVector = info->idCache.find(nameAttr);
 356             if (!nameVector) {
 357                 nameVector = new QPtrVector<NodeImpl>;
 358                 info->nameCache.insert(nameAttr, nameVector);
 359             }
 360             appendToVector(nameVector, n);
 361         }
 362     }
 363
 364     info->hasNameCache = true;
 365 }
 366
 367 QValueList<Node> HTMLCollectionImpl::namedItems(const DOMString &name) const
 368 {
 369     QValueList<Node> result;
 370
 371     if (name.isEmpty())
 372         return result;
 373
 374     resetCollectionInfo();
 375     updateNameCache();
 376
 377     QPtrVector<NodeImpl> *idResults = info->idCache.find(name.string());
 378     QPtrVector<NodeImpl> *nameResults = info->nameCache.find(name.string());
 379
 380     for (unsigned i = 0; idResults && i < idResults->count(); ++i) {
 381         result.append(idResults->at(i));
 382     }
 383
 384     for (unsigned i = 0; nameResults && i < nameResults->count(); ++i) {
 385         result.append(nameResults->at(i));
 386     }
 387
 388     return result;
 389 }
 390
 391
 392 NodeImpl *HTMLCollectionImpl::nextNamedItem( const DOMString &name ) const
 393 {
 394     resetCollectionInfo();
 395
 396     for (NodeImpl *n = traverseNextItem(info->current ? info->current : base); n; n = traverseNextItem(n)) {
 397         if (checkForNameMatch(n, idsDone, name, true)) {
 398             info->current = n;
 399             return n;
 400         }
 401     }
 402
 403     if (idsDone) {
 404         info->current = 0;
 405         return 0;
 406     }
 407     idsDone = true;
 408
 409     for (NodeImpl *n = traverseNextItem(info->current ? info->current : base); n; n = traverseNextItem(n)) {
 410         if (checkForNameMatch(n, idsDone, name, true)) {
 411             info->current = n;
 412             return n;
 413         }
 414     }
 415
 416     return 0;
 417 }
 418
 419 // -----------------------------------------------------------------------------
 420
 421 HTMLFormCollectionImpl::HTMLFormCollectionImpl(NodeImpl* _base)
 422     : HTMLCollectionImpl(_base, 0)
 423 {
 424     HTMLFormElementImpl *formBase = static_cast<HTMLFormElementImpl*>(base);
 425     if (!formBase->collectionInfo) {
 426         formBase->collectionInfo = new CollectionInfo();
 427     }
 428     info = formBase->collectionInfo;
 429 }
 430
 431 HTMLFormCollectionImpl::~HTMLFormCollectionImpl()
 432 {
 433 }
 434
 435 unsigned long HTMLFormCollectionImpl::calcLength() const
 436 {
 437     QPtrVector<HTMLGenericFormElementImpl> &l = static_cast<HTMLFormElementImpl*>( base )->formElements;
 438
 439     int len = 0;
 440     for ( unsigned i = 0; i < l.count(); i++ )
 441         if ( l.at( i )->isEnumeratable() )
 442             ++len;
 443
 444     return len;
 445 }
 446
 447 NodeImpl *HTMLFormCollectionImpl::item(unsigned long index) const
 448 {
 449     resetCollectionInfo();
 450
 451     if (info->current && info->position == index) {
 452         return info->current;
 453     }
 454     if (info->haslength && info->length <= index) {
 455         return 0;
 456     }
 457     if (!info->current || info->position > index) {
 458         info->current = 0;
 459         info->position = 0;
 460         info->elementsArrayPosition = 0;
 461     }
 462
 463     QPtrVector<HTMLGenericFormElementImpl> &l = static_cast<HTMLFormElementImpl*>( base )->formElements;
 464     unsigned currentIndex = info->position;
 465
 466     for (unsigned i = info->elementsArrayPosition; i < l.count(); i++) {
 467         if (l[i]->isEnumeratable() ) {
 468             if (index == currentIndex) {
 469                 info->position = index;
 470                 info->current = l[i];
 471                 info->elementsArrayPosition = i;
 472                 return l[i];
 473             }
 474
 475             currentIndex++;
 476         }
 477     }
 478
 479     return 0;
 480 }
 481
 482 NodeImpl* HTMLFormCollectionImpl::getNamedItem(NodeImpl*, int attr_id, const DOMString& name, bool caseSensitive) const
 483 {
 484     info->position = 0;
 485     return getNamedFormItem( attr_id, name, 0, caseSensitive );
 486 }
 487
 488 NodeImpl* HTMLFormCollectionImpl::getNamedFormItem(int attr_id, const DOMString& name, int duplicateNumber, bool caseSensitive) const
 489 {
 490     if(base->nodeType() == Node::ELEMENT_NODE)
 491     {
 492         HTMLElementImpl* baseElement = static_cast<HTMLElementImpl*>(base);
 493         bool foundInputElements = false;
 494         if(baseElement->id() == ID_FORM)
 495         {
 496             HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(baseElement);
 497             for (unsigned i = 0; i < f->formElements.count(); ++i) {
 498                 HTMLGenericFormElementImpl* e = f->formElements[i];
 499                 if (e->isEnumeratable()) {
 500                     bool found;
 501                     if (caseSensitive)
 502                         found = e->getAttribute(attr_id) == name;
 503                     else
 504                         found = e->getAttribute(attr_id).domString().lower() == name.lower();
 505                     if (found) {
 506                         foundInputElements = true;
 507                         if (!duplicateNumber)
 508                             return e;
 509                         --duplicateNumber;
 510                     }
 511                 }
 512             }
 513         }
 514
 515         if ( !foundInputElements )
 516         {
 517             HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(baseElement);
 518
 519             for(unsigned i = 0; i < f->imgElements.count(); ++i)
 520             {
 521                 HTMLImageElementImpl* e = f->imgElements[i];
 522                 bool found;
 523                 if (caseSensitive)
 524                     found = e->getAttribute(attr_id) == name;
 525                 else
 526                     found = e->getAttribute(attr_id).domString().lower() == name.lower();
 527                 if (found) {
 528                     if (!duplicateNumber)
 529                         return e;
 530                     --duplicateNumber;
 531                 }
 532             }
 533         }
 534     }
 535     return 0;
 536 }
 537
 538 NodeImpl * HTMLFormCollectionImpl::firstItem() const
 539 {
 540     return item(0);
 541 }
 542
 543 NodeImpl * HTMLFormCollectionImpl::nextItem() const
 544 {
 545     return item(info->position + 1);
 546 }
 547
 548 NodeImpl * HTMLFormCollectionImpl::nextNamedItemInternal( const DOMString &name ) const
 549 {
 550     NodeImpl *retval = getNamedFormItem( idsDone ? ATTR_NAME : ATTR_ID, name, ++info->position, true );
 551     if ( retval )
 552         return retval;
 553     if ( idsDone ) // we're done
 554         return 0;
 555     // After doing all ATTR_ID, do ATTR_NAME
 556     idsDone = true;
 557     return getNamedItem(base->firstChild(), ATTR_NAME, name, true);
 558 }
 559
 560 NodeImpl *HTMLFormCollectionImpl::namedItem( const DOMString &name, bool caseSensitive ) const
 561 {
 562     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
 563     // This method first searches for an object with a matching id
 564     // attribute. If a match is not found, the method then searches for an
 565     // object with a matching name attribute, but only on those elements
 566     // that are allowed a name attribute.
 567     resetCollectionInfo();
 568     idsDone = false;
 569     info->current = getNamedItem(base->firstChild(), ATTR_ID, name, true);
 570     if(info->current)
 571         return info->current;
 572     idsDone = true;
 573     info->current = getNamedItem(base->firstChild(), ATTR_NAME, name, true);
 574     return info->current;
 575 }
 576
 577
 578 NodeImpl *HTMLFormCollectionImpl::nextNamedItem( const DOMString &name ) const
 579 {
 580     // nextNamedItemInternal can return an item that has both id=<name> and name=<name>
 581     // Here, we have to filter out such cases.
 582     NodeImpl *impl = nextNamedItemInternal( name );
 583     if (!idsDone) // looking for id=<name> -> no filtering
 584         return impl;
 585     // looking for name=<name> -> filter out if id=<name>
 586     bool ok = false;
 587     while (impl && !ok)
 588     {
 589         if(impl->nodeType() == Node::ELEMENT_NODE)
 590         {
 591             HTMLElementImpl *e = static_cast<HTMLElementImpl *>(impl);
 592             ok = (e->getAttribute(ATTR_ID) != name);
 593             if (!ok)
 594                 impl = nextNamedItemInternal( name );
 595         } else // can't happen
 596             ok = true;
 597     }
 598     return impl;
 599 }
 600
 601 void HTMLFormCollectionImpl::updateNameCache() const
 602 {
 603     if (info->hasNameCache)
 604         return;
 605
 606     QDict<char> foundInputElements;
 607
 608     if (base->nodeType() != Node::ELEMENT_NODE ||static_cast<HTMLElementImpl*>(base)->id() != ID_FORM) {
 609         info->hasNameCache = true;
 610         return;
 611     }
 612
 613     HTMLElementImpl* baseElement = static_cast<HTMLElementImpl*>(base);
 614
 615     HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(baseElement);
 616     for (unsigned i = 0; i < f->formElements.count(); ++i) {
 617         HTMLGenericFormElementImpl* e = f->formElements[i];
 618         if (e->isEnumeratable()) {
 619             QString idAttr = e->getAttribute(ATTR_ID).string();
 620             QString nameAttr = e->getAttribute(ATTR_NAME).string();
 621             if (!idAttr.isEmpty()) {
 622                 // add to id cache
 623                 QPtrVector<NodeImpl> *idVector = info->idCache.find(idAttr);
 624                 if (!idVector) {
 625                     idVector = new QPtrVector<NodeImpl>;
 626                     info->idCache.insert(idAttr, idVector);
 627                 }
 628                 appendToVector(idVector, static_cast<NodeImpl *>(e));
 629                 foundInputElements.insert(idAttr, (char *)true);
 630             }
 631             if (!nameAttr.isEmpty() && idAttr != nameAttr) {
 632                 // add to name cache
 633                 QPtrVector<NodeImpl> *nameVector = info->nameCache.find(nameAttr);
 634                 if (!nameVector) {
 635                     nameVector = new QPtrVector<NodeImpl>;
 636                     info->nameCache.insert(nameAttr, nameVector);
 637                 }
 638                 appendToVector(nameVector, static_cast<NodeImpl *>(e));
 639                 foundInputElements.insert(nameAttr, (char *)true);
 640             }
 641         }
 642     }
 643
 644     for (unsigned i = 0; i < f->imgElements.count(); ++i) {
 645         HTMLImageElementImpl* e = f->imgElements[i];
 646         QString idAttr = e->getAttribute(ATTR_ID).string();
 647         QString nameAttr = e->getAttribute(ATTR_NAME).string();
 648         if (!idAttr.isEmpty() && !foundInputElements.find(idAttr)) {
 649             // add to id cache
 650             QPtrVector<NodeImpl> *idVector = info->idCache.find(idAttr);
 651             if (!idVector) {
 652                 idVector = new QPtrVector<NodeImpl>;
 653                 info->idCache.insert(idAttr, idVector);
 654             }
 655             appendToVector(idVector, static_cast<NodeImpl *>(e));
 656         }
 657         if (!nameAttr.isEmpty() && idAttr != nameAttr && !foundInputElements.find(nameAttr)) {
 658             // add to name cache
 659             QPtrVector<NodeImpl> *nameVector = info->idCache.find(nameAttr);
 660             if (!nameVector) {
 661                 nameVector = new QPtrVector<NodeImpl>;
 662                 info->nameCache.insert(nameAttr, nameVector);
 663             }
 664             appendToVector(nameVector, static_cast<NodeImpl *>(e));
 665         }
 666     }
 667
 668     info->hasNameCache = true;
 669 }