6815f25ffd41166abd0f89800f43866ad5640f98
[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();
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 }