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