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