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