]> dev.renevier.net Git - syp.git/blob - openlayers/tools/BeautifulSoup.py
fixes notices
[syp.git] / openlayers / tools / BeautifulSoup.py
1 """Beautiful Soup
2 Elixir and Tonic
3 "The Screen-Scraper's Friend"
4 http://www.crummy.com/software/BeautifulSoup/
5
6 Beautiful Soup parses a (possibly invalid) XML or HTML document into a
7 tree representation. It provides methods and Pythonic idioms that make
8 it easy to navigate, search, and modify the tree.
9
10 A well-formed XML/HTML document yields a well-formed data
11 structure. An ill-formed XML/HTML document yields a correspondingly
12 ill-formed data structure. If your document is only locally
13 well-formed, you can use this library to find and process the
14 well-formed part of it. The BeautifulSoup class 
15
16 Beautiful Soup works with Python 2.2 and up. It has no external
17 dependencies, but you'll have more success at converting data to UTF-8
18 if you also install these three packages:
19
20 * chardet, for auto-detecting character encodings
21   http://chardet.feedparser.org/
22 * cjkcodecs and iconv_codec, which add more encodings to the ones supported
23   by stock Python.
24   http://cjkpython.i18n.org/
25
26 Beautiful Soup defines classes for two main parsing strategies:
27     
28  * BeautifulStoneSoup, for parsing XML, SGML, or your domain-specific
29    language that kind of looks like XML.
30
31  * BeautifulSoup, for parsing run-of-the-mill HTML code, be it valid
32    or invalid. This class has web browser-like heuristics for
33    obtaining a sensible parse tree in the face of common HTML errors.
34
35 Beautiful Soup also defines a class (UnicodeDammit) for autodetecting
36 the encoding of an HTML or XML document, and converting it to
37 Unicode. Much of this code is taken from Mark Pilgrim's Universal Feed Parser.
38
39 For more than you ever wanted to know about Beautiful Soup, see the
40 documentation:
41 http://www.crummy.com/software/BeautifulSoup/documentation.html
42
43 """
44 from __future__ import generators
45
46 __author__ = "Leonard Richardson (leonardr@segfault.org)"
47 __version__ = "3.0.4"
48 __copyright__ = "Copyright (c) 2004-2007 Leonard Richardson"
49 __license__ = "PSF"
50
51 from sgmllib import SGMLParser, SGMLParseError
52 import codecs
53 import types
54 import re
55 import sgmllib
56 try:
57   from htmlentitydefs import name2codepoint
58 except ImportError:
59   name2codepoint = {}
60
61 #This hack makes Beautiful Soup able to parse XML with namespaces
62 sgmllib.tagfind = re.compile('[a-zA-Z][-_.:a-zA-Z0-9]*')
63
64 DEFAULT_OUTPUT_ENCODING = "utf-8"
65
66 # First, the classes that represent markup elements.
67
68 class PageElement:
69     """Contains the navigational information for some part of the page
70     (either a tag or a piece of text)"""
71
72     def setup(self, parent=None, previous=None):
73         """Sets up the initial relations between this element and
74         other elements."""        
75         self.parent = parent
76         self.previous = previous
77         self.next = None
78         self.previousSibling = None
79         self.nextSibling = None
80         if self.parent and self.parent.contents:
81             self.previousSibling = self.parent.contents[-1]
82             self.previousSibling.nextSibling = self
83
84     def replaceWith(self, replaceWith):        
85         oldParent = self.parent
86         myIndex = self.parent.contents.index(self)
87         if hasattr(replaceWith, 'parent') and replaceWith.parent == self.parent:
88             # We're replacing this element with one of its siblings.
89             index = self.parent.contents.index(replaceWith)
90             if index and index < myIndex:
91                 # Furthermore, it comes before this element. That
92                 # means that when we extract it, the index of this
93                 # element will change.
94                 myIndex = myIndex - 1
95         self.extract()        
96         oldParent.insert(myIndex, replaceWith)
97         
98     def extract(self):
99         """Destructively rips this element out of the tree."""        
100         if self.parent:
101             try:
102                 self.parent.contents.remove(self)
103             except ValueError:
104                 pass
105
106         #Find the two elements that would be next to each other if
107         #this element (and any children) hadn't been parsed. Connect
108         #the two.        
109         lastChild = self._lastRecursiveChild()
110         nextElement = lastChild.next
111
112         if self.previous:
113             self.previous.next = nextElement
114         if nextElement:
115             nextElement.previous = self.previous
116         self.previous = None
117         lastChild.next = None
118
119         self.parent = None        
120         if self.previousSibling:
121             self.previousSibling.nextSibling = self.nextSibling
122         if self.nextSibling:
123             self.nextSibling.previousSibling = self.previousSibling
124         self.previousSibling = self.nextSibling = None       
125
126     def _lastRecursiveChild(self):
127         "Finds the last element beneath this object to be parsed."
128         lastChild = self
129         while hasattr(lastChild, 'contents') and lastChild.contents:
130             lastChild = lastChild.contents[-1]
131         return lastChild
132
133     def insert(self, position, newChild):
134         if (isinstance(newChild, basestring)
135             or isinstance(newChild, unicode)) \
136             and not isinstance(newChild, NavigableString):
137             newChild = NavigableString(newChild)        
138
139         position =  min(position, len(self.contents))
140         if hasattr(newChild, 'parent') and newChild.parent != None:
141             # We're 'inserting' an element that's already one
142             # of this object's children. 
143             if newChild.parent == self:
144                 index = self.find(newChild)
145                 if index and index < position:
146                     # Furthermore we're moving it further down the
147                     # list of this object's children. That means that
148                     # when we extract this element, our target index
149                     # will jump down one.
150                     position = position - 1
151             newChild.extract()
152             
153         newChild.parent = self
154         previousChild = None
155         if position == 0:
156             newChild.previousSibling = None
157             newChild.previous = self
158         else:
159             previousChild = self.contents[position-1]
160             newChild.previousSibling = previousChild
161             newChild.previousSibling.nextSibling = newChild
162             newChild.previous = previousChild._lastRecursiveChild()
163         if newChild.previous:
164             newChild.previous.next = newChild        
165
166         newChildsLastElement = newChild._lastRecursiveChild()
167
168         if position >= len(self.contents):
169             newChild.nextSibling = None
170             
171             parent = self
172             parentsNextSibling = None
173             while not parentsNextSibling:
174                 parentsNextSibling = parent.nextSibling
175                 parent = parent.parent
176                 if not parent: # This is the last element in the document.
177                     break
178             if parentsNextSibling:
179                 newChildsLastElement.next = parentsNextSibling
180             else:
181                 newChildsLastElement.next = None
182         else:
183             nextChild = self.contents[position]            
184             newChild.nextSibling = nextChild            
185             if newChild.nextSibling:
186                 newChild.nextSibling.previousSibling = newChild
187             newChildsLastElement.next = nextChild
188
189         if newChildsLastElement.next:
190             newChildsLastElement.next.previous = newChildsLastElement
191         self.contents.insert(position, newChild)
192
193     def findNext(self, name=None, attrs={}, text=None, **kwargs):
194         """Returns the first item that matches the given criteria and
195         appears after this Tag in the document."""
196         return self._findOne(self.findAllNext, name, attrs, text, **kwargs)
197
198     def findAllNext(self, name=None, attrs={}, text=None, limit=None,
199                     **kwargs):
200         """Returns all items that match the given criteria and appear
201         before after Tag in the document."""
202         return self._findAll(name, attrs, text, limit, self.nextGenerator)
203
204     def findNextSibling(self, name=None, attrs={}, text=None, **kwargs):
205         """Returns the closest sibling to this Tag that matches the
206         given criteria and appears after this Tag in the document."""
207         return self._findOne(self.findNextSiblings, name, attrs, text,
208                              **kwargs)
209
210     def findNextSiblings(self, name=None, attrs={}, text=None, limit=None,
211                          **kwargs):
212         """Returns the siblings of this Tag that match the given
213         criteria and appear after this Tag in the document."""
214         return self._findAll(name, attrs, text, limit,
215                              self.nextSiblingGenerator, **kwargs)
216     fetchNextSiblings = findNextSiblings # Compatibility with pre-3.x
217
218     def findPrevious(self, name=None, attrs={}, text=None, **kwargs):
219         """Returns the first item that matches the given criteria and
220         appears before this Tag in the document."""
221         return self._findOne(self.findAllPrevious, name, attrs, text, **kwargs)
222
223     def findAllPrevious(self, name=None, attrs={}, text=None, limit=None,
224                         **kwargs):
225         """Returns all items that match the given criteria and appear
226         before this Tag in the document."""
227         return self._findAll(name, attrs, text, limit, self.previousGenerator,
228                            **kwargs)
229     fetchPrevious = findAllPrevious # Compatibility with pre-3.x
230
231     def findPreviousSibling(self, name=None, attrs={}, text=None, **kwargs):
232         """Returns the closest sibling to this Tag that matches the
233         given criteria and appears before this Tag in the document."""
234         return self._findOne(self.findPreviousSiblings, name, attrs, text,
235                              **kwargs)
236
237     def findPreviousSiblings(self, name=None, attrs={}, text=None,
238                              limit=None, **kwargs):
239         """Returns the siblings of this Tag that match the given
240         criteria and appear before this Tag in the document."""
241         return self._findAll(name, attrs, text, limit,
242                              self.previousSiblingGenerator, **kwargs)
243     fetchPreviousSiblings = findPreviousSiblings # Compatibility with pre-3.x
244
245     def findParent(self, name=None, attrs={}, **kwargs):
246         """Returns the closest parent of this Tag that matches the given
247         criteria."""
248         # NOTE: We can't use _findOne because findParents takes a different
249         # set of arguments.
250         r = None
251         l = self.findParents(name, attrs, 1)
252         if l:
253             r = l[0]
254         return r
255
256     def findParents(self, name=None, attrs={}, limit=None, **kwargs):
257         """Returns the parents of this Tag that match the given
258         criteria."""
259
260         return self._findAll(name, attrs, None, limit, self.parentGenerator,
261                              **kwargs)
262     fetchParents = findParents # Compatibility with pre-3.x
263
264     #These methods do the real heavy lifting.
265
266     def _findOne(self, method, name, attrs, text, **kwargs):
267         r = None
268         l = method(name, attrs, text, 1, **kwargs)
269         if l:
270             r = l[0]
271         return r
272     
273     def _findAll(self, name, attrs, text, limit, generator, **kwargs):
274         "Iterates over a generator looking for things that match."
275
276         if isinstance(name, SoupStrainer):
277             strainer = name
278         else:
279             # Build a SoupStrainer
280             strainer = SoupStrainer(name, attrs, text, **kwargs)
281         results = ResultSet(strainer)
282         g = generator()
283         while True:
284             try:
285                 i = g.next()
286             except StopIteration:
287                 break
288             if i:
289                 found = strainer.search(i)
290                 if found:
291                     results.append(found)
292                     if limit and len(results) >= limit:
293                         break
294         return results
295
296     #These Generators can be used to navigate starting from both
297     #NavigableStrings and Tags.                
298     def nextGenerator(self):
299         i = self
300         while i:
301             i = i.next
302             yield i
303
304     def nextSiblingGenerator(self):
305         i = self
306         while i:
307             i = i.nextSibling
308             yield i
309
310     def previousGenerator(self):
311         i = self
312         while i:
313             i = i.previous
314             yield i
315
316     def previousSiblingGenerator(self):
317         i = self
318         while i:
319             i = i.previousSibling
320             yield i
321
322     def parentGenerator(self):
323         i = self
324         while i:
325             i = i.parent
326             yield i
327
328     # Utility methods
329     def substituteEncoding(self, str, encoding=None):
330         encoding = encoding or "utf-8"
331         return str.replace("%SOUP-ENCODING%", encoding)    
332
333     def toEncoding(self, s, encoding=None):
334         """Encodes an object to a string in some encoding, or to Unicode.
335         ."""
336         if isinstance(s, unicode):
337             if encoding:
338                 s = s.encode(encoding)
339         elif isinstance(s, str):
340             if encoding:
341                 s = s.encode(encoding)
342             else:
343                 s = unicode(s)
344         else:
345             if encoding:
346                 s  = self.toEncoding(str(s), encoding)
347             else:
348                 s = unicode(s)
349         return s
350
351 class NavigableString(unicode, PageElement):
352
353     def __getattr__(self, attr):
354         """text.string gives you text. This is for backwards
355         compatibility for Navigable*String, but for CData* it lets you
356         get the string without the CData wrapper."""
357         if attr == 'string':
358             return self
359         else:
360             raise AttributeError, "'%s' object has no attribute '%s'" % (self.__class__.__name__, attr)
361
362     def __unicode__(self):
363         return self.__str__(None)
364
365     def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING):
366         if encoding:
367             return self.encode(encoding)
368         else:
369             return self
370         
371 class CData(NavigableString):
372
373     def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING):
374         return "<![CDATA[%s]]>" % NavigableString.__str__(self, encoding)
375
376 class ProcessingInstruction(NavigableString):
377     def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING):
378         output = self
379         if "%SOUP-ENCODING%" in output:
380             output = self.substituteEncoding(output, encoding)
381         return "<?%s?>" % self.toEncoding(output, encoding)
382
383 class Comment(NavigableString):
384     def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING):
385         return "<!--%s-->" % NavigableString.__str__(self, encoding)    
386
387 class Declaration(NavigableString):
388     def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING):
389         return "<!%s>" % NavigableString.__str__(self, encoding)        
390
391 class Tag(PageElement):
392
393     """Represents a found HTML tag with its attributes and contents."""
394
395     XML_SPECIAL_CHARS_TO_ENTITIES = { "'" : "squot",
396                                       '"' : "quote",
397                                       "&" : "amp",
398                                       "<" : "lt",
399                                       ">" : "gt" }
400
401     def __init__(self, parser, name, attrs=None, parent=None,
402                  previous=None):
403         "Basic constructor."
404
405         # We don't actually store the parser object: that lets extracted
406         # chunks be garbage-collected
407         self.parserClass = parser.__class__
408         self.isSelfClosing = parser.isSelfClosingTag(name)
409         self.name = name
410         if attrs == None:
411             attrs = []
412         self.attrs = attrs
413         self.contents = []
414         self.setup(parent, previous)
415         self.hidden = False
416         self.containsSubstitutions = False
417
418     def get(self, key, default=None):
419         """Returns the value of the 'key' attribute for the tag, or
420         the value given for 'default' if it doesn't have that
421         attribute."""
422         return self._getAttrMap().get(key, default)    
423
424     def has_key(self, key):
425         return self._getAttrMap().has_key(key)
426
427     def __getitem__(self, key):
428         """tag[key] returns the value of the 'key' attribute for the tag,
429         and throws an exception if it's not there."""
430         return self._getAttrMap()[key]
431
432     def __iter__(self):
433         "Iterating over a tag iterates over its contents."
434         return iter(self.contents)
435
436     def __len__(self):
437         "The length of a tag is the length of its list of contents."
438         return len(self.contents)
439
440     def __contains__(self, x):
441         return x in self.contents
442
443     def __nonzero__(self):
444         "A tag is non-None even if it has no contents."
445         return True
446
447     def __setitem__(self, key, value):        
448         """Setting tag[key] sets the value of the 'key' attribute for the
449         tag."""
450         self._getAttrMap()
451         self.attrMap[key] = value
452         found = False
453         for i in range(0, len(self.attrs)):
454             if self.attrs[i][0] == key:
455                 self.attrs[i] = (key, value)
456                 found = True
457         if not found:
458             self.attrs.append((key, value))
459         self._getAttrMap()[key] = value
460
461     def __delitem__(self, key):
462         "Deleting tag[key] deletes all 'key' attributes for the tag."
463         for item in self.attrs:
464             if item[0] == key:
465                 self.attrs.remove(item)
466                 #We don't break because bad HTML can define the same
467                 #attribute multiple times.
468             self._getAttrMap()
469             if self.attrMap.has_key(key):
470                 del self.attrMap[key]
471
472     def __call__(self, *args, **kwargs):
473         """Calling a tag like a function is the same as calling its
474         findAll() method. Eg. tag('a') returns a list of all the A tags
475         found within this tag."""
476         return apply(self.findAll, args, kwargs)
477
478     def __getattr__(self, tag):
479         #print "Getattr %s.%s" % (self.__class__, tag)
480         if len(tag) > 3 and tag.rfind('Tag') == len(tag)-3:
481             return self.find(tag[:-3])
482         elif tag.find('__') != 0:
483             return self.find(tag)
484
485     def __eq__(self, other):
486         """Returns true iff this tag has the same name, the same attributes,
487         and the same contents (recursively) as the given tag.
488
489         NOTE: right now this will return false if two tags have the
490         same attributes in a different order. Should this be fixed?"""
491         if not hasattr(other, 'name') or not hasattr(other, 'attrs') or not hasattr(other, 'contents') or self.name != other.name or self.attrs != other.attrs or len(self) != len(other):
492             return False
493         for i in range(0, len(self.contents)):
494             if self.contents[i] != other.contents[i]:
495                 return False
496         return True
497
498     def __ne__(self, other):
499         """Returns true iff this tag is not identical to the other tag,
500         as defined in __eq__."""
501         return not self == other
502
503     def __repr__(self, encoding=DEFAULT_OUTPUT_ENCODING):
504         """Renders this tag as a string."""
505         return self.__str__(encoding)
506
507     def __unicode__(self):
508         return self.__str__(None)
509
510     def __str__(self, encoding=DEFAULT_OUTPUT_ENCODING,
511                 prettyPrint=False, indentLevel=0):
512         """Returns a string or Unicode representation of this tag and
513         its contents. To get Unicode, pass None for encoding.
514
515         NOTE: since Python's HTML parser consumes whitespace, this
516         method is not certain to reproduce the whitespace present in
517         the original string."""
518
519         encodedName = self.toEncoding(self.name, encoding)
520
521         attrs = []
522         if self.attrs:
523             for key, val in self.attrs:
524                 fmt = '%s="%s"'
525                 if isString(val):                    
526                     if self.containsSubstitutions and '%SOUP-ENCODING%' in val:
527                         val = self.substituteEncoding(val, encoding)
528
529                     # The attribute value either:
530                     #
531                     # * Contains no embedded double quotes or single quotes.
532                     #   No problem: we enclose it in double quotes.
533                     # * Contains embedded single quotes. No problem:
534                     #   double quotes work here too.
535                     # * Contains embedded double quotes. No problem:
536                     #   we enclose it in single quotes.
537                     # * Embeds both single _and_ double quotes. This
538                     #   can't happen naturally, but it can happen if
539                     #   you modify an attribute value after parsing
540                     #   the document. Now we have a bit of a
541                     #   problem. We solve it by enclosing the
542                     #   attribute in single quotes, and escaping any
543                     #   embedded single quotes to XML entities.
544                     if '"' in val:
545                         fmt = "%s='%s'"
546                         # This can't happen naturally, but it can happen
547                         # if you modify an attribute value after parsing.
548                         if "'" in val:
549                             val = val.replace("'", "&squot;")
550
551                     # Now we're okay w/r/t quotes. But the attribute
552                     # value might also contain angle brackets, or
553                     # ampersands that aren't part of entities. We need
554                     # to escape those to XML entities too.
555                     val = re.sub("([<>]|&(?![^\s]+;))",
556                                  lambda x: "&" + self.XML_SPECIAL_CHARS_TO_ENTITIES[x.group(0)[0]] + ";",
557                                  val)
558                                       
559                 attrs.append(fmt % (self.toEncoding(key, encoding),
560                                     self.toEncoding(val, encoding)))
561         close = ''
562         closeTag = ''
563         if self.isSelfClosing:
564             close = ' /'
565         else:
566             closeTag = '</%s>' % encodedName
567
568         indentTag, indentContents = 0, 0
569         if prettyPrint:
570             indentTag = indentLevel
571             space = (' ' * (indentTag-1))
572             indentContents = indentTag + 1
573         contents = self.renderContents(encoding, prettyPrint, indentContents)
574         if self.hidden:
575             s = contents
576         else:
577             s = []
578             attributeString = ''
579             if attrs:
580                 attributeString = ' ' + ' '.join(attrs)            
581             if prettyPrint:
582                 s.append(space)
583             s.append('<%s%s%s>' % (encodedName, attributeString, close))
584             if prettyPrint:
585                 s.append("\n")
586             s.append(contents)
587             if prettyPrint and contents and contents[-1] != "\n":
588                 s.append("\n")
589             if prettyPrint and closeTag:
590                 s.append(space)
591             s.append(closeTag)
592             if prettyPrint and closeTag and self.nextSibling:
593                 s.append("\n")
594             s = ''.join(s)
595         return s
596
597     def prettify(self, encoding=DEFAULT_OUTPUT_ENCODING):
598         return self.__str__(encoding, True)
599
600     def renderContents(self, encoding=DEFAULT_OUTPUT_ENCODING,
601                        prettyPrint=False, indentLevel=0):
602         """Renders the contents of this tag as a string in the given
603         encoding. If encoding is None, returns a Unicode string.."""
604         s=[]
605         for c in self:
606             text = None
607             if isinstance(c, NavigableString):
608                 text = c.__str__(encoding)
609             elif isinstance(c, Tag):
610                 s.append(c.__str__(encoding, prettyPrint, indentLevel))
611             if text and prettyPrint:
612                 text = text.strip()              
613             if text:
614                 if prettyPrint:
615                     s.append(" " * (indentLevel-1))
616                 s.append(text)
617                 if prettyPrint:
618                     s.append("\n")
619         return ''.join(s)    
620
621     #Soup methods
622
623     def find(self, name=None, attrs={}, recursive=True, text=None,
624              **kwargs):
625         """Return only the first child of this Tag matching the given
626         criteria."""
627         r = None
628         l = self.findAll(name, attrs, recursive, text, 1, **kwargs)
629         if l:
630             r = l[0]
631         return r
632     findChild = find
633
634     def findAll(self, name=None, attrs={}, recursive=True, text=None,
635                 limit=None, **kwargs):
636         """Extracts a list of Tag objects that match the given
637         criteria.  You can specify the name of the Tag and any
638         attributes you want the Tag to have.
639
640         The value of a key-value pair in the 'attrs' map can be a
641         string, a list of strings, a regular expression object, or a
642         callable that takes a string and returns whether or not the
643         string matches for some custom definition of 'matches'. The
644         same is true of the tag name."""
645         generator = self.recursiveChildGenerator
646         if not recursive:
647             generator = self.childGenerator
648         return self._findAll(name, attrs, text, limit, generator, **kwargs)
649     findChildren = findAll
650
651     # Pre-3.x compatibility methods
652     first = find
653     fetch = findAll
654     
655     def fetchText(self, text=None, recursive=True, limit=None):
656         return self.findAll(text=text, recursive=recursive, limit=limit)
657
658     def firstText(self, text=None, recursive=True):
659         return self.find(text=text, recursive=recursive)
660     
661     #Utility methods
662
663     def append(self, tag):
664         """Appends the given tag to the contents of this tag."""
665         self.contents.append(tag)
666
667     #Private methods
668
669     def _getAttrMap(self):
670         """Initializes a map representation of this tag's attributes,
671         if not already initialized."""
672         if not getattr(self, 'attrMap'):
673             self.attrMap = {}
674             for (key, value) in self.attrs:
675                 self.attrMap[key] = value 
676         return self.attrMap
677
678     #Generator methods
679     def childGenerator(self):
680         for i in range(0, len(self.contents)):
681             yield self.contents[i]
682         raise StopIteration
683     
684     def recursiveChildGenerator(self):
685         stack = [(self, 0)]
686         while stack:
687             tag, start = stack.pop()
688             if isinstance(tag, Tag):            
689                 for i in range(start, len(tag.contents)):
690                     a = tag.contents[i]
691                     yield a
692                     if isinstance(a, Tag) and tag.contents:
693                         if i < len(tag.contents) - 1:
694                             stack.append((tag, i+1))
695                         stack.append((a, 0))
696                         break
697         raise StopIteration
698
699 # Next, a couple classes to represent queries and their results.
700 class SoupStrainer:
701     """Encapsulates a number of ways of matching a markup element (tag or
702     text)."""
703
704     def __init__(self, name=None, attrs={}, text=None, **kwargs):
705         self.name = name
706         if isString(attrs):
707             kwargs['class'] = attrs
708             attrs = None
709         if kwargs:
710             if attrs:
711                 attrs = attrs.copy()
712                 attrs.update(kwargs)
713             else:
714                 attrs = kwargs
715         self.attrs = attrs
716         self.text = text
717
718     def __str__(self):
719         if self.text:
720             return self.text
721         else:
722             return "%s|%s" % (self.name, self.attrs)
723     
724     def searchTag(self, markupName=None, markupAttrs={}):
725         found = None
726         markup = None
727         if isinstance(markupName, Tag):
728             markup = markupName
729             markupAttrs = markup
730         callFunctionWithTagData = callable(self.name) \
731                                 and not isinstance(markupName, Tag)
732
733         if (not self.name) \
734                or callFunctionWithTagData \
735                or (markup and self._matches(markup, self.name)) \
736                or (not markup and self._matches(markupName, self.name)):
737             if callFunctionWithTagData:
738                 match = self.name(markupName, markupAttrs)
739             else:
740                 match = True            
741                 markupAttrMap = None
742                 for attr, matchAgainst in self.attrs.items():
743                     if not markupAttrMap:
744                          if hasattr(markupAttrs, 'get'):
745                             markupAttrMap = markupAttrs
746                          else:
747                             markupAttrMap = {}
748                             for k,v in markupAttrs:
749                                 markupAttrMap[k] = v
750                     attrValue = markupAttrMap.get(attr)
751                     if not self._matches(attrValue, matchAgainst):
752                         match = False
753                         break
754             if match:
755                 if markup:
756                     found = markup
757                 else:
758                     found = markupName
759         return found
760
761     def search(self, markup):
762         #print 'looking for %s in %s' % (self, markup)
763         found = None
764         # If given a list of items, scan it for a text element that
765         # matches.        
766         if isList(markup) and not isinstance(markup, Tag):
767             for element in markup:
768                 if isinstance(element, NavigableString) \
769                        and self.search(element):
770                     found = element
771                     break
772         # If it's a Tag, make sure its name or attributes match.
773         # Don't bother with Tags if we're searching for text.
774         elif isinstance(markup, Tag):
775             if not self.text:
776                 found = self.searchTag(markup)
777         # If it's text, make sure the text matches.
778         elif isinstance(markup, NavigableString) or \
779                  isString(markup):
780             if self._matches(markup, self.text):
781                 found = markup
782         else:
783             raise Exception, "I don't know how to match against a %s" \
784                   % markup.__class__
785         return found
786         
787     def _matches(self, markup, matchAgainst):    
788         #print "Matching %s against %s" % (markup, matchAgainst)
789         result = False
790         if matchAgainst == True and type(matchAgainst) == types.BooleanType:
791             result = markup != None
792         elif callable(matchAgainst):
793             result = matchAgainst(markup)
794         else:
795             #Custom match methods take the tag as an argument, but all
796             #other ways of matching match the tag name as a string.
797             if isinstance(markup, Tag):
798                 markup = markup.name
799             if markup and not isString(markup):
800                 markup = unicode(markup)
801             #Now we know that chunk is either a string, or None.
802             if hasattr(matchAgainst, 'match'):
803                 # It's a regexp object.
804                 result = markup and matchAgainst.search(markup)
805             elif isList(matchAgainst):
806                 result = markup in matchAgainst
807             elif hasattr(matchAgainst, 'items'):
808                 result = markup.has_key(matchAgainst)
809             elif matchAgainst and isString(markup):
810                 if isinstance(markup, unicode):
811                     matchAgainst = unicode(matchAgainst)
812                 else:
813                     matchAgainst = str(matchAgainst)
814
815             if not result:
816                 result = matchAgainst == markup
817         return result
818
819 class ResultSet(list):
820     """A ResultSet is just a list that keeps track of the SoupStrainer
821     that created it."""
822     def __init__(self, source):
823         list.__init__([])
824         self.source = source
825
826 # Now, some helper functions.
827
828 def isList(l):
829     """Convenience method that works with all 2.x versions of Python
830     to determine whether or not something is listlike."""
831     return hasattr(l, '__iter__') \
832            or (type(l) in (types.ListType, types.TupleType))
833
834 def isString(s):
835     """Convenience method that works with all 2.x versions of Python
836     to determine whether or not something is stringlike."""
837     try:
838         return isinstance(s, unicode) or isintance(s, basestring) 
839     except NameError:
840         return isinstance(s, str)
841
842 def buildTagMap(default, *args):
843     """Turns a list of maps, lists, or scalars into a single map.
844     Used to build the SELF_CLOSING_TAGS, NESTABLE_TAGS, and
845     NESTING_RESET_TAGS maps out of lists and partial maps."""
846     built = {}
847     for portion in args:
848         if hasattr(portion, 'items'):
849             #It's a map. Merge it.
850             for k,v in portion.items():
851                 built[k] = v
852         elif isList(portion):
853             #It's a list. Map each item to the default.
854             for k in portion:
855                 built[k] = default
856         else:
857             #It's a scalar. Map it to the default.
858             built[portion] = default
859     return built
860
861 # Now, the parser classes.
862
863 class BeautifulStoneSoup(Tag, SGMLParser):
864
865     """This class contains the basic parser and search code. It defines
866     a parser that knows nothing about tag behavior except for the
867     following:
868    
869       You can't close a tag without closing all the tags it encloses.
870       That is, "<foo><bar></foo>" actually means
871       "<foo><bar></bar></foo>".
872
873     [Another possible explanation is "<foo><bar /></foo>", but since
874     this class defines no SELF_CLOSING_TAGS, it will never use that
875     explanation.]
876
877     This class is useful for parsing XML or made-up markup languages,
878     or when BeautifulSoup makes an assumption counter to what you were
879     expecting."""
880
881     XML_ENTITY_LIST = {}
882     for i in Tag.XML_SPECIAL_CHARS_TO_ENTITIES.values():
883         XML_ENTITY_LIST[i] = True 
884
885     SELF_CLOSING_TAGS = {}
886     NESTABLE_TAGS = {}
887     RESET_NESTING_TAGS = {}
888     QUOTE_TAGS = {}
889
890     MARKUP_MASSAGE = [(re.compile('(<[^<>]*)/>'),
891                        lambda x: x.group(1) + ' />'),
892                       (re.compile('<!\s+([^<>]*)>'),
893                        lambda x: '<!' + x.group(1) + '>')
894                       ]
895
896     ROOT_TAG_NAME = u'[document]'
897
898     HTML_ENTITIES = "html"
899     XML_ENTITIES = "xml"
900
901     def __init__(self, markup="", parseOnlyThese=None, fromEncoding=None,
902                  markupMassage=True, smartQuotesTo=XML_ENTITIES,
903                  convertEntities=None, selfClosingTags=None):
904         """The Soup object is initialized as the 'root tag', and the
905         provided markup (which can be a string or a file-like object)
906         is fed into the underlying parser. 
907
908         sgmllib will process most bad HTML, and the BeautifulSoup
909         class has some tricks for dealing with some HTML that kills
910         sgmllib, but Beautiful Soup can nonetheless choke or lose data
911         if your data uses self-closing tags or declarations
912         incorrectly.
913
914         By default, Beautiful Soup uses regexes to sanitize input,
915         avoiding the vast majority of these problems. If the problems
916         don't apply to you, pass in False for markupMassage, and
917         you'll get better performance.
918
919         The default parser massage techniques fix the two most common
920         instances of invalid HTML that choke sgmllib:
921
922          <br/> (No space between name of closing tag and tag close)
923          <! --Comment--> (Extraneous whitespace in declaration)
924
925         You can pass in a custom list of (RE object, replace method)
926         tuples to get Beautiful Soup to scrub your input the way you
927         want."""
928
929         self.parseOnlyThese = parseOnlyThese
930         self.fromEncoding = fromEncoding
931         self.smartQuotesTo = smartQuotesTo
932         self.convertEntities = convertEntities
933         if self.convertEntities:
934             # It doesn't make sense to convert encoded characters to
935             # entities even while you're converting entities to Unicode.
936             # Just convert it all to Unicode.
937             self.smartQuotesTo = None
938         self.instanceSelfClosingTags = buildTagMap(None, selfClosingTags)
939         SGMLParser.__init__(self)
940             
941         if hasattr(markup, 'read'):        # It's a file-type object.
942             markup = markup.read()
943         self.markup = markup
944         self.markupMassage = markupMassage
945         try:
946             self._feed()
947         except StopParsing:
948             pass
949         self.markup = None                 # The markup can now be GCed
950         
951     def _feed(self, inDocumentEncoding=None):
952         # Convert the document to Unicode.
953         markup = self.markup
954         if isinstance(markup, unicode):
955             if not hasattr(self, 'originalEncoding'):
956                 self.originalEncoding = None
957         else:
958             dammit = UnicodeDammit\
959                      (markup, [self.fromEncoding, inDocumentEncoding],
960                       smartQuotesTo=self.smartQuotesTo)
961             markup = dammit.unicode
962             self.originalEncoding = dammit.originalEncoding
963         if markup:
964             if self.markupMassage:
965                 if not isList(self.markupMassage):
966                     self.markupMassage = self.MARKUP_MASSAGE            
967                 for fix, m in self.markupMassage:
968                     markup = fix.sub(m, markup)
969         self.reset()
970
971         SGMLParser.feed(self, markup)
972         # Close out any unfinished strings and close all the open tags.
973         self.endData()
974         while self.currentTag.name != self.ROOT_TAG_NAME:
975             self.popTag()
976
977     def __getattr__(self, methodName):
978         """This method routes method call requests to either the SGMLParser
979         superclass or the Tag superclass, depending on the method name."""
980         #print "__getattr__ called on %s.%s" % (self.__class__, methodName)
981
982         if methodName.find('start_') == 0 or methodName.find('end_') == 0 \
983                or methodName.find('do_') == 0:
984             return SGMLParser.__getattr__(self, methodName)
985         elif methodName.find('__') != 0:
986             return Tag.__getattr__(self, methodName)
987         else:
988             raise AttributeError
989
990     def isSelfClosingTag(self, name):
991         """Returns true iff the given string is the name of a
992         self-closing tag according to this parser."""
993         return self.SELF_CLOSING_TAGS.has_key(name) \
994                or self.instanceSelfClosingTags.has_key(name)
995             
996     def reset(self):
997         Tag.__init__(self, self, self.ROOT_TAG_NAME)
998         self.hidden = 1
999         SGMLParser.reset(self)
1000         self.currentData = []
1001         self.currentTag = None
1002         self.tagStack = []
1003         self.quoteStack = []
1004         self.pushTag(self)
1005     
1006     def popTag(self):
1007         tag = self.tagStack.pop()
1008         # Tags with just one string-owning child get the child as a
1009         # 'string' property, so that soup.tag.string is shorthand for
1010         # soup.tag.contents[0]
1011         if len(self.currentTag.contents) == 1 and \
1012            isinstance(self.currentTag.contents[0], NavigableString):
1013             self.currentTag.string = self.currentTag.contents[0]
1014
1015         #print "Pop", tag.name
1016         if self.tagStack:
1017             self.currentTag = self.tagStack[-1]
1018         return self.currentTag
1019
1020     def pushTag(self, tag):
1021         #print "Push", tag.name
1022         if self.currentTag:
1023             self.currentTag.append(tag)
1024         self.tagStack.append(tag)
1025         self.currentTag = self.tagStack[-1]
1026
1027     def endData(self, containerClass=NavigableString):
1028         if self.currentData:
1029             currentData = ''.join(self.currentData)
1030             if not currentData.strip():
1031                 if '\n' in currentData:
1032                     currentData = '\n'
1033                 else:
1034                     currentData = ' '
1035             self.currentData = []
1036             if self.parseOnlyThese and len(self.tagStack) <= 1 and \
1037                    (not self.parseOnlyThese.text or \
1038                     not self.parseOnlyThese.search(currentData)):
1039                 return
1040             o = containerClass(currentData)
1041             o.setup(self.currentTag, self.previous)
1042             if self.previous:
1043                 self.previous.next = o
1044             self.previous = o
1045             self.currentTag.contents.append(o)
1046
1047
1048     def _popToTag(self, name, inclusivePop=True):
1049         """Pops the tag stack up to and including the most recent
1050         instance of the given tag. If inclusivePop is false, pops the tag
1051         stack up to but *not* including the most recent instqance of
1052         the given tag."""
1053         #print "Popping to %s" % name
1054         if name == self.ROOT_TAG_NAME:
1055             return            
1056
1057         numPops = 0
1058         mostRecentTag = None
1059         for i in range(len(self.tagStack)-1, 0, -1):
1060             if name == self.tagStack[i].name:
1061                 numPops = len(self.tagStack)-i
1062                 break
1063         if not inclusivePop:
1064             numPops = numPops - 1
1065
1066         for i in range(0, numPops):
1067             mostRecentTag = self.popTag()
1068         return mostRecentTag    
1069
1070     def _smartPop(self, name):
1071
1072         """We need to pop up to the previous tag of this type, unless
1073         one of this tag's nesting reset triggers comes between this
1074         tag and the previous tag of this type, OR unless this tag is a
1075         generic nesting trigger and another generic nesting trigger
1076         comes between this tag and the previous tag of this type.
1077
1078         Examples:
1079          <p>Foo<b>Bar<p> should pop to 'p', not 'b'.
1080          <p>Foo<table>Bar<p> should pop to 'table', not 'p'.
1081          <p>Foo<table><tr>Bar<p> should pop to 'tr', not 'p'.
1082          <p>Foo<b>Bar<p> should pop to 'p', not 'b'.
1083
1084          <li><ul><li> *<li>* should pop to 'ul', not the first 'li'.
1085          <tr><table><tr> *<tr>* should pop to 'table', not the first 'tr'
1086          <td><tr><td> *<td>* should pop to 'tr', not the first 'td'
1087         """
1088
1089         nestingResetTriggers = self.NESTABLE_TAGS.get(name)
1090         isNestable = nestingResetTriggers != None
1091         isResetNesting = self.RESET_NESTING_TAGS.has_key(name)
1092         popTo = None
1093         inclusive = True
1094         for i in range(len(self.tagStack)-1, 0, -1):
1095             p = self.tagStack[i]
1096             if (not p or p.name == name) and not isNestable:
1097                 #Non-nestable tags get popped to the top or to their
1098                 #last occurance.
1099                 popTo = name
1100                 break
1101             if (nestingResetTriggers != None
1102                 and p.name in nestingResetTriggers) \
1103                 or (nestingResetTriggers == None and isResetNesting
1104                     and self.RESET_NESTING_TAGS.has_key(p.name)):
1105                 
1106                 #If we encounter one of the nesting reset triggers
1107                 #peculiar to this tag, or we encounter another tag
1108                 #that causes nesting to reset, pop up to but not
1109                 #including that tag.
1110                 popTo = p.name
1111                 inclusive = False
1112                 break
1113             p = p.parent
1114         if popTo:
1115             self._popToTag(popTo, inclusive)
1116
1117     def unknown_starttag(self, name, attrs, selfClosing=0):
1118         #print "Start tag %s: %s" % (name, attrs)
1119         if self.quoteStack:
1120             #This is not a real tag.
1121             #print "<%s> is not real!" % name
1122             attrs = ''.join(map(lambda(x, y): ' %s="%s"' % (x, y), attrs))
1123             self.handle_data('<%s%s>' % (name, attrs))
1124             return        
1125         self.endData()
1126
1127         if not self.isSelfClosingTag(name) and not selfClosing:
1128             self._smartPop(name)
1129
1130         if self.parseOnlyThese and len(self.tagStack) <= 1 \
1131                and (self.parseOnlyThese.text or not self.parseOnlyThese.searchTag(name, attrs)):
1132             return
1133
1134         tag = Tag(self, name, attrs, self.currentTag, self.previous)
1135         if self.previous:
1136             self.previous.next = tag
1137         self.previous = tag
1138         self.pushTag(tag)
1139         if selfClosing or self.isSelfClosingTag(name):
1140             self.popTag()                
1141         if name in self.QUOTE_TAGS:
1142             #print "Beginning quote (%s)" % name
1143             self.quoteStack.append(name)
1144             self.literal = 1
1145         return tag
1146
1147     def unknown_endtag(self, name):
1148         #print "End tag %s" % name
1149         if self.quoteStack and self.quoteStack[-1] != name:
1150             #This is not a real end tag.
1151             #print "</%s> is not real!" % name
1152             self.handle_data('</%s>' % name)
1153             return
1154         self.endData()
1155         self._popToTag(name)
1156         if self.quoteStack and self.quoteStack[-1] == name:
1157             self.quoteStack.pop()
1158             self.literal = (len(self.quoteStack) > 0)
1159
1160     def handle_data(self, data):
1161         self.currentData.append(data)
1162
1163     def _toStringSubclass(self, text, subclass):
1164         """Adds a certain piece of text to the tree as a NavigableString
1165         subclass."""
1166         self.endData()
1167         self.handle_data(text)
1168         self.endData(subclass)
1169
1170     def handle_pi(self, text):
1171         """Handle a processing instruction as a ProcessingInstruction
1172         object, possibly one with a %SOUP-ENCODING% slot into which an
1173         encoding will be plugged later."""
1174         if text[:3] == "xml":
1175             text = "xml version='1.0' encoding='%SOUP-ENCODING%'"
1176         self._toStringSubclass(text, ProcessingInstruction)
1177
1178     def handle_comment(self, text):
1179         "Handle comments as Comment objects."
1180         self._toStringSubclass(text, Comment)
1181
1182     def handle_charref(self, ref):
1183         "Handle character references as data."
1184         if self.convertEntities in [self.HTML_ENTITIES,
1185                                     self.XML_ENTITIES]:
1186             data = unichr(int(ref))
1187         else:
1188             data = '&#%s;' % ref
1189         self.handle_data(data)
1190
1191     def handle_entityref(self, ref):
1192         """Handle entity references as data, possibly converting known
1193         HTML entity references to the corresponding Unicode
1194         characters."""
1195         data = None
1196         if self.convertEntities == self.HTML_ENTITIES or \
1197                (self.convertEntities == self.XML_ENTITIES and \
1198                 self.XML_ENTITY_LIST.get(ref)):
1199             try:
1200                 data = unichr(name2codepoint[ref])
1201             except KeyError:
1202                 pass
1203         if not data:
1204             data = '&%s;' % ref
1205         self.handle_data(data)
1206         
1207     def handle_decl(self, data):
1208         "Handle DOCTYPEs and the like as Declaration objects."
1209         self._toStringSubclass(data, Declaration)
1210
1211     def parse_declaration(self, i):
1212         """Treat a bogus SGML declaration as raw data. Treat a CDATA
1213         declaration as a CData object."""
1214         j = None
1215         if self.rawdata[i:i+9] == '<![CDATA[':
1216              k = self.rawdata.find(']]>', i)
1217              if k == -1:
1218                  k = len(self.rawdata)
1219              data = self.rawdata[i+9:k]
1220              j = k+3
1221              self._toStringSubclass(data, CData)
1222         else:
1223             try:
1224                 j = SGMLParser.parse_declaration(self, i)
1225             except SGMLParseError:
1226                 toHandle = self.rawdata[i:]
1227                 self.handle_data(toHandle)
1228                 j = i + len(toHandle)
1229         return j
1230
1231 class BeautifulSoup(BeautifulStoneSoup):
1232
1233     """This parser knows the following facts about HTML:
1234
1235     * Some tags have no closing tag and should be interpreted as being
1236       closed as soon as they are encountered.
1237
1238     * The text inside some tags (ie. 'script') may contain tags which
1239       are not really part of the document and which should be parsed
1240       as text, not tags. If you want to parse the text as tags, you can
1241       always fetch it and parse it explicitly.
1242
1243     * Tag nesting rules:
1244
1245       Most tags can't be nested at all. For instance, the occurance of
1246       a <p> tag should implicitly close the previous <p> tag.
1247
1248        <p>Para1<p>Para2
1249         should be transformed into:
1250        <p>Para1</p><p>Para2
1251
1252       Some tags can be nested arbitrarily. For instance, the occurance
1253       of a <blockquote> tag should _not_ implicitly close the previous
1254       <blockquote> tag.
1255
1256        Alice said: <blockquote>Bob said: <blockquote>Blah
1257         should NOT be transformed into:
1258        Alice said: <blockquote>Bob said: </blockquote><blockquote>Blah
1259
1260       Some tags can be nested, but the nesting is reset by the
1261       interposition of other tags. For instance, a <tr> tag should
1262       implicitly close the previous <tr> tag within the same <table>,
1263       but not close a <tr> tag in another table.
1264
1265        <table><tr>Blah<tr>Blah
1266         should be transformed into:
1267        <table><tr>Blah</tr><tr>Blah
1268         but,
1269        <tr>Blah<table><tr>Blah
1270         should NOT be transformed into
1271        <tr>Blah<table></tr><tr>Blah
1272
1273     Differing assumptions about tag nesting rules are a major source
1274     of problems with the BeautifulSoup class. If BeautifulSoup is not
1275     treating as nestable a tag your page author treats as nestable,
1276     try ICantBelieveItsBeautifulSoup, MinimalSoup, or
1277     BeautifulStoneSoup before writing your own subclass."""
1278
1279     def __init__(self, *args, **kwargs):
1280         if not kwargs.has_key('smartQuotesTo'):
1281             kwargs['smartQuotesTo'] = self.HTML_ENTITIES
1282         BeautifulStoneSoup.__init__(self, *args, **kwargs)
1283
1284     SELF_CLOSING_TAGS = buildTagMap(None,
1285                                     ['br' , 'hr', 'input', 'img', 'meta',
1286                                     'spacer', 'link', 'frame', 'base'])
1287
1288     QUOTE_TAGS = {'script': None}
1289     
1290     #According to the HTML standard, each of these inline tags can
1291     #contain another tag of the same type. Furthermore, it's common
1292     #to actually use these tags this way.
1293     NESTABLE_INLINE_TAGS = ['span', 'font', 'q', 'object', 'bdo', 'sub', 'sup',
1294                             'center']
1295
1296     #According to the HTML standard, these block tags can contain
1297     #another tag of the same type. Furthermore, it's common
1298     #to actually use these tags this way.
1299     NESTABLE_BLOCK_TAGS = ['blockquote', 'div', 'fieldset', 'ins', 'del']
1300
1301     #Lists can contain other lists, but there are restrictions.    
1302     NESTABLE_LIST_TAGS = { 'ol' : [],
1303                            'ul' : [],
1304                            'li' : ['ul', 'ol'],
1305                            'dl' : [],
1306                            'dd' : ['dl'],
1307                            'dt' : ['dl'] }
1308
1309     #Tables can contain other tables, but there are restrictions.    
1310     NESTABLE_TABLE_TAGS = {'table' : [], 
1311                            'tr' : ['table', 'tbody', 'tfoot', 'thead'],
1312                            'td' : ['tr'],
1313                            'th' : ['tr'],
1314                            'thead' : ['table'],
1315                            'tbody' : ['table'],
1316                            'tfoot' : ['table'],
1317                            }
1318
1319     NON_NESTABLE_BLOCK_TAGS = ['address', 'form', 'p', 'pre']
1320
1321     #If one of these tags is encountered, all tags up to the next tag of
1322     #this type are popped.
1323     RESET_NESTING_TAGS = buildTagMap(None, NESTABLE_BLOCK_TAGS, 'noscript',
1324                                      NON_NESTABLE_BLOCK_TAGS,
1325                                      NESTABLE_LIST_TAGS,
1326                                      NESTABLE_TABLE_TAGS)
1327
1328     NESTABLE_TAGS = buildTagMap([], NESTABLE_INLINE_TAGS, NESTABLE_BLOCK_TAGS,
1329                                 NESTABLE_LIST_TAGS, NESTABLE_TABLE_TAGS)
1330
1331     # Used to detect the charset in a META tag; see start_meta
1332     CHARSET_RE = re.compile("((^|;)\s*charset=)([^;]*)")
1333
1334     def start_meta(self, attrs):
1335         """Beautiful Soup can detect a charset included in a META tag,
1336         try to convert the document to that charset, and re-parse the
1337         document from the beginning."""
1338         httpEquiv = None
1339         contentType = None
1340         contentTypeIndex = None
1341         tagNeedsEncodingSubstitution = False
1342
1343         for i in range(0, len(attrs)):
1344             key, value = attrs[i]
1345             key = key.lower()
1346             if key == 'http-equiv':
1347                 httpEquiv = value
1348             elif key == 'content':
1349                 contentType = value
1350                 contentTypeIndex = i
1351
1352         if httpEquiv and contentType: # It's an interesting meta tag.
1353             match = self.CHARSET_RE.search(contentType)
1354             if match:
1355                 if getattr(self, 'declaredHTMLEncoding') or \
1356                        (self.originalEncoding == self.fromEncoding):
1357                     # This is our second pass through the document, or
1358                     # else an encoding was specified explicitly and it
1359                     # worked. Rewrite the meta tag.
1360                     newAttr = self.CHARSET_RE.sub\
1361                               (lambda(match):match.group(1) +
1362                                "%SOUP-ENCODING%", value)
1363                     attrs[contentTypeIndex] = (attrs[contentTypeIndex][0],
1364                                                newAttr)
1365                     tagNeedsEncodingSubstitution = True
1366                 else:
1367                     # This is our first pass through the document.
1368                     # Go through it again with the new information.
1369                     newCharset = match.group(3)
1370                     if newCharset and newCharset != self.originalEncoding:
1371                         self.declaredHTMLEncoding = newCharset
1372                         self._feed(self.declaredHTMLEncoding)
1373                         raise StopParsing
1374         tag = self.unknown_starttag("meta", attrs)
1375         if tag and tagNeedsEncodingSubstitution:
1376             tag.containsSubstitutions = True
1377
1378 class StopParsing(Exception):
1379     pass
1380    
1381 class ICantBelieveItsBeautifulSoup(BeautifulSoup):
1382
1383     """The BeautifulSoup class is oriented towards skipping over
1384     common HTML errors like unclosed tags. However, sometimes it makes
1385     errors of its own. For instance, consider this fragment:
1386
1387      <b>Foo<b>Bar</b></b>
1388
1389     This is perfectly valid (if bizarre) HTML. However, the
1390     BeautifulSoup class will implicitly close the first b tag when it
1391     encounters the second 'b'. It will think the author wrote
1392     "<b>Foo<b>Bar", and didn't close the first 'b' tag, because
1393     there's no real-world reason to bold something that's already
1394     bold. When it encounters '</b></b>' it will close two more 'b'
1395     tags, for a grand total of three tags closed instead of two. This
1396     can throw off the rest of your document structure. The same is
1397     true of a number of other tags, listed below.
1398
1399     It's much more common for someone to forget to close a 'b' tag
1400     than to actually use nested 'b' tags, and the BeautifulSoup class
1401     handles the common case. This class handles the not-co-common
1402     case: where you can't believe someone wrote what they did, but
1403     it's valid HTML and BeautifulSoup screwed up by assuming it
1404     wouldn't be."""
1405
1406     I_CANT_BELIEVE_THEYRE_NESTABLE_INLINE_TAGS = \
1407      ['em', 'big', 'i', 'small', 'tt', 'abbr', 'acronym', 'strong',
1408       'cite', 'code', 'dfn', 'kbd', 'samp', 'strong', 'var', 'b',
1409       'big']
1410
1411     I_CANT_BELIEVE_THEYRE_NESTABLE_BLOCK_TAGS = ['noscript']
1412
1413     NESTABLE_TAGS = buildTagMap([], BeautifulSoup.NESTABLE_TAGS,
1414                                 I_CANT_BELIEVE_THEYRE_NESTABLE_BLOCK_TAGS,
1415                                 I_CANT_BELIEVE_THEYRE_NESTABLE_INLINE_TAGS)
1416
1417 class MinimalSoup(BeautifulSoup):
1418     """The MinimalSoup class is for parsing HTML that contains
1419     pathologically bad markup. It makes no assumptions about tag
1420     nesting, but it does know which tags are self-closing, that
1421     <script> tags contain Javascript and should not be parsed, that
1422     META tags may contain encoding information, and so on.
1423
1424     This also makes it better for subclassing than BeautifulStoneSoup
1425     or BeautifulSoup."""
1426     
1427     RESET_NESTING_TAGS = buildTagMap('noscript')
1428     NESTABLE_TAGS = {}
1429
1430 class BeautifulSOAP(BeautifulStoneSoup):
1431     """This class will push a tag with only a single string child into
1432     the tag's parent as an attribute. The attribute's name is the tag
1433     name, and the value is the string child. An example should give
1434     the flavor of the change:
1435
1436     <foo><bar>baz</bar></foo>
1437      =>
1438     <foo bar="baz"><bar>baz</bar></foo>
1439
1440     You can then access fooTag['bar'] instead of fooTag.barTag.string.
1441
1442     This is, of course, useful for scraping structures that tend to
1443     use subelements instead of attributes, such as SOAP messages. Note
1444     that it modifies its input, so don't print the modified version
1445     out.
1446
1447     I'm not sure how many people really want to use this class; let me
1448     know if you do. Mainly I like the name."""
1449
1450     def popTag(self):
1451         if len(self.tagStack) > 1:
1452             tag = self.tagStack[-1]
1453             parent = self.tagStack[-2]
1454             parent._getAttrMap()
1455             if (isinstance(tag, Tag) and len(tag.contents) == 1 and
1456                 isinstance(tag.contents[0], NavigableString) and 
1457                 not parent.attrMap.has_key(tag.name)):
1458                 parent[tag.name] = tag.contents[0]
1459         BeautifulStoneSoup.popTag(self)
1460
1461 #Enterprise class names! It has come to our attention that some people
1462 #think the names of the Beautiful Soup parser classes are too silly
1463 #and "unprofessional" for use in enterprise screen-scraping. We feel
1464 #your pain! For such-minded folk, the Beautiful Soup Consortium And
1465 #All-Night Kosher Bakery recommends renaming this file to
1466 #"RobustParser.py" (or, in cases of extreme enterprisness,
1467 #"RobustParserBeanInterface.class") and using the following
1468 #enterprise-friendly class aliases:
1469 class RobustXMLParser(BeautifulStoneSoup):
1470     pass
1471 class RobustHTMLParser(BeautifulSoup):
1472     pass
1473 class RobustWackAssHTMLParser(ICantBelieveItsBeautifulSoup):
1474     pass
1475 class RobustInsanelyWackAssHTMLParser(MinimalSoup):
1476     pass
1477 class SimplifyingSOAPParser(BeautifulSOAP):
1478     pass
1479
1480 ######################################################
1481 #
1482 # Bonus library: Unicode, Dammit
1483 #
1484 # This class forces XML data into a standard format (usually to UTF-8
1485 # or Unicode).  It is heavily based on code from Mark Pilgrim's
1486 # Universal Feed Parser. It does not rewrite the XML or HTML to
1487 # reflect a new encoding: that happens in BeautifulStoneSoup.handle_pi
1488 # (XML) and BeautifulSoup.start_meta (HTML).
1489
1490 # Autodetects character encodings.
1491 # Download from http://chardet.feedparser.org/
1492 try:
1493     import chardet
1494 #    import chardet.constants
1495 #    chardet.constants._debug = 1
1496 except:
1497     chardet = None
1498 chardet = None
1499
1500 # cjkcodecs and iconv_codec make Python know about more character encodings.
1501 # Both are available from http://cjkpython.i18n.org/
1502 # They're built in if you use Python 2.4.
1503 try:
1504     import cjkcodecs.aliases
1505 except:
1506     pass
1507 try:
1508     import iconv_codec
1509 except:
1510     pass
1511
1512 class UnicodeDammit:
1513     """A class for detecting the encoding of a *ML document and
1514     converting it to a Unicode string. If the source encoding is
1515     windows-1252, can replace MS smart quotes with their HTML or XML
1516     equivalents."""
1517
1518     # This dictionary maps commonly seen values for "charset" in HTML
1519     # meta tags to the corresponding Python codec names. It only covers
1520     # values that aren't in Python's aliases and can't be determined
1521     # by the heuristics in find_codec.
1522     CHARSET_ALIASES = { "macintosh" : "mac-roman",
1523                         "x-sjis" : "shift-jis" }
1524
1525     def __init__(self, markup, overrideEncodings=[],
1526                  smartQuotesTo='xml'):
1527         self.markup, documentEncoding, sniffedEncoding = \
1528                      self._detectEncoding(markup)
1529         self.smartQuotesTo = smartQuotesTo
1530         self.triedEncodings = []
1531         if markup == '' or isinstance(markup, unicode):
1532             self.originalEncoding = None
1533             self.unicode = unicode(markup)            
1534             return
1535         
1536         u = None
1537         for proposedEncoding in overrideEncodings:
1538             u = self._convertFrom(proposedEncoding)
1539             if u: break
1540         if not u:
1541             for proposedEncoding in (documentEncoding, sniffedEncoding):
1542                 u = self._convertFrom(proposedEncoding)
1543                 if u: break
1544                 
1545         # If no luck and we have auto-detection library, try that:
1546         if not u and chardet and not isinstance(self.markup, unicode):
1547             u = self._convertFrom(chardet.detect(self.markup)['encoding'])
1548
1549         # As a last resort, try utf-8 and windows-1252:
1550         if not u:
1551             for proposed_encoding in ("utf-8", "windows-1252"):
1552                 u = self._convertFrom(proposed_encoding)
1553                 if u: break
1554         self.unicode = u
1555         if not u: self.originalEncoding = None
1556
1557     def _subMSChar(self, orig):
1558         """Changes a MS smart quote character to an XML or HTML
1559         entity."""
1560         sub = self.MS_CHARS.get(orig)
1561         if type(sub) == types.TupleType:
1562             if self.smartQuotesTo == 'xml':
1563                 sub = '&#x%s;' % sub[1]
1564             else:
1565                 sub = '&%s;' % sub[0]
1566         return sub            
1567
1568     def _convertFrom(self, proposed):        
1569         proposed = self.find_codec(proposed)
1570         if not proposed or proposed in self.triedEncodings:
1571             return None
1572         self.triedEncodings.append(proposed)
1573         markup = self.markup
1574
1575         # Convert smart quotes to HTML if coming from an encoding
1576         # that might have them.
1577         if self.smartQuotesTo and proposed.lower() in("windows-1252",
1578                                                       "iso-8859-1",
1579                                                       "iso-8859-2"):
1580             markup = re.compile("([\x80-\x9f])").sub \
1581                      (lambda(x): self._subMSChar(x.group(1)),
1582                       markup)
1583
1584         try:
1585             # print "Trying to convert document to %s" % proposed
1586             u = self._toUnicode(markup, proposed)
1587             self.markup = u       
1588             self.originalEncoding = proposed
1589         except Exception, e:
1590             # print "That didn't work!"
1591             # print e
1592             return None        
1593         #print "Correct encoding: %s" % proposed
1594         return self.markup
1595
1596     def _toUnicode(self, data, encoding):
1597         '''Given a string and its encoding, decodes the string into Unicode.
1598         %encoding is a string recognized by encodings.aliases'''
1599
1600         # strip Byte Order Mark (if present)
1601         if (len(data) >= 4) and (data[:2] == '\xfe\xff') \
1602                and (data[2:4] != '\x00\x00'):
1603             encoding = 'utf-16be'
1604             data = data[2:]
1605         elif (len(data) >= 4) and (data[:2] == '\xff\xfe') \
1606                  and (data[2:4] != '\x00\x00'):
1607             encoding = 'utf-16le'
1608             data = data[2:]
1609         elif data[:3] == '\xef\xbb\xbf':
1610             encoding = 'utf-8'
1611             data = data[3:]
1612         elif data[:4] == '\x00\x00\xfe\xff':
1613             encoding = 'utf-32be'
1614             data = data[4:]
1615         elif data[:4] == '\xff\xfe\x00\x00':
1616             encoding = 'utf-32le'
1617             data = data[4:]
1618         newdata = unicode(data, encoding)
1619         return newdata
1620     
1621     def _detectEncoding(self, xml_data):
1622         """Given a document, tries to detect its XML encoding."""
1623         xml_encoding = sniffed_xml_encoding = None
1624         try:
1625             if xml_data[:4] == '\x4c\x6f\xa7\x94':
1626                 # EBCDIC
1627                 xml_data = self._ebcdic_to_ascii(xml_data)
1628             elif xml_data[:4] == '\x00\x3c\x00\x3f':
1629                 # UTF-16BE
1630                 sniffed_xml_encoding = 'utf-16be'
1631                 xml_data = unicode(xml_data, 'utf-16be').encode('utf-8')
1632             elif (len(xml_data) >= 4) and (xml_data[:2] == '\xfe\xff') \
1633                      and (xml_data[2:4] != '\x00\x00'):
1634                 # UTF-16BE with BOM
1635                 sniffed_xml_encoding = 'utf-16be'
1636                 xml_data = unicode(xml_data[2:], 'utf-16be').encode('utf-8')
1637             elif xml_data[:4] == '\x3c\x00\x3f\x00':
1638                 # UTF-16LE
1639                 sniffed_xml_encoding = 'utf-16le'
1640                 xml_data = unicode(xml_data, 'utf-16le').encode('utf-8')
1641             elif (len(xml_data) >= 4) and (xml_data[:2] == '\xff\xfe') and \
1642                      (xml_data[2:4] != '\x00\x00'):
1643                 # UTF-16LE with BOM
1644                 sniffed_xml_encoding = 'utf-16le'
1645                 xml_data = unicode(xml_data[2:], 'utf-16le').encode('utf-8')
1646             elif xml_data[:4] == '\x00\x00\x00\x3c':
1647                 # UTF-32BE
1648                 sniffed_xml_encoding = 'utf-32be'
1649                 xml_data = unicode(xml_data, 'utf-32be').encode('utf-8')
1650             elif xml_data[:4] == '\x3c\x00\x00\x00':
1651                 # UTF-32LE
1652                 sniffed_xml_encoding = 'utf-32le'
1653                 xml_data = unicode(xml_data, 'utf-32le').encode('utf-8')
1654             elif xml_data[:4] == '\x00\x00\xfe\xff':
1655                 # UTF-32BE with BOM
1656                 sniffed_xml_encoding = 'utf-32be'
1657                 xml_data = unicode(xml_data[4:], 'utf-32be').encode('utf-8')
1658             elif xml_data[:4] == '\xff\xfe\x00\x00':
1659                 # UTF-32LE with BOM
1660                 sniffed_xml_encoding = 'utf-32le'
1661                 xml_data = unicode(xml_data[4:], 'utf-32le').encode('utf-8')
1662             elif xml_data[:3] == '\xef\xbb\xbf':
1663                 # UTF-8 with BOM
1664                 sniffed_xml_encoding = 'utf-8'
1665                 xml_data = unicode(xml_data[3:], 'utf-8').encode('utf-8')
1666             else:
1667                 sniffed_xml_encoding = 'ascii'
1668                 pass
1669             xml_encoding_match = re.compile \
1670                                  ('^<\?.*encoding=[\'"](.*?)[\'"].*\?>')\
1671                                  .match(xml_data)
1672         except:
1673             xml_encoding_match = None
1674         if xml_encoding_match:
1675             xml_encoding = xml_encoding_match.groups()[0].lower()
1676             if sniffed_xml_encoding and \
1677                (xml_encoding in ('iso-10646-ucs-2', 'ucs-2', 'csunicode',
1678                                  'iso-10646-ucs-4', 'ucs-4', 'csucs4',
1679                                  'utf-16', 'utf-32', 'utf_16', 'utf_32',
1680                                  'utf16', 'u16')):
1681                 xml_encoding = sniffed_xml_encoding
1682         return xml_data, xml_encoding, sniffed_xml_encoding
1683
1684
1685     def find_codec(self, charset):
1686         return self._codec(self.CHARSET_ALIASES.get(charset, charset)) \
1687                or (charset and self._codec(charset.replace("-", ""))) \
1688                or (charset and self._codec(charset.replace("-", "_"))) \
1689                or charset
1690
1691     def _codec(self, charset):
1692         if not charset: return charset 
1693         codec = None
1694         try:
1695             codecs.lookup(charset)
1696             codec = charset
1697         except LookupError:
1698             pass
1699         return codec
1700
1701     EBCDIC_TO_ASCII_MAP = None
1702     def _ebcdic_to_ascii(self, s):
1703         c = self.__class__
1704         if not c.EBCDIC_TO_ASCII_MAP:
1705             emap = (0,1,2,3,156,9,134,127,151,141,142,11,12,13,14,15,
1706                     16,17,18,19,157,133,8,135,24,25,146,143,28,29,30,31,
1707                     128,129,130,131,132,10,23,27,136,137,138,139,140,5,6,7,
1708                     144,145,22,147,148,149,150,4,152,153,154,155,20,21,158,26,
1709                     32,160,161,162,163,164,165,166,167,168,91,46,60,40,43,33,
1710                     38,169,170,171,172,173,174,175,176,177,93,36,42,41,59,94,
1711                     45,47,178,179,180,181,182,183,184,185,124,44,37,95,62,63,
1712                     186,187,188,189,190,191,192,193,194,96,58,35,64,39,61,34,
1713                     195,97,98,99,100,101,102,103,104,105,196,197,198,199,200,
1714                     201,202,106,107,108,109,110,111,112,113,114,203,204,205,
1715                     206,207,208,209,126,115,116,117,118,119,120,121,122,210,
1716                     211,212,213,214,215,216,217,218,219,220,221,222,223,224,
1717                     225,226,227,228,229,230,231,123,65,66,67,68,69,70,71,72,
1718                     73,232,233,234,235,236,237,125,74,75,76,77,78,79,80,81,
1719                     82,238,239,240,241,242,243,92,159,83,84,85,86,87,88,89,
1720                     90,244,245,246,247,248,249,48,49,50,51,52,53,54,55,56,57,
1721                     250,251,252,253,254,255)
1722             import string
1723             c.EBCDIC_TO_ASCII_MAP = string.maketrans( \
1724             ''.join(map(chr, range(256))), ''.join(map(chr, emap)))
1725         return s.translate(c.EBCDIC_TO_ASCII_MAP)
1726
1727     MS_CHARS = { '\x80' : ('euro', '20AC'),
1728                  '\x81' : ' ',
1729                  '\x82' : ('sbquo', '201A'),
1730                  '\x83' : ('fnof', '192'),
1731                  '\x84' : ('bdquo', '201E'),
1732                  '\x85' : ('hellip', '2026'),
1733                  '\x86' : ('dagger', '2020'),
1734                  '\x87' : ('Dagger', '2021'),
1735                  '\x88' : ('circ', '2C6'),
1736                  '\x89' : ('permil', '2030'),
1737                  '\x8A' : ('Scaron', '160'),
1738                  '\x8B' : ('lsaquo', '2039'),
1739                  '\x8C' : ('OElig', '152'),
1740                  '\x8D' : '?',
1741                  '\x8E' : ('#x17D', '17D'),
1742                  '\x8F' : '?',
1743                  '\x90' : '?',
1744                  '\x91' : ('lsquo', '2018'),
1745                  '\x92' : ('rsquo', '2019'),
1746                  '\x93' : ('ldquo', '201C'),
1747                  '\x94' : ('rdquo', '201D'),
1748                  '\x95' : ('bull', '2022'),
1749                  '\x96' : ('ndash', '2013'),
1750                  '\x97' : ('mdash', '2014'),
1751                  '\x98' : ('tilde', '2DC'),
1752                  '\x99' : ('trade', '2122'),
1753                  '\x9a' : ('scaron', '161'),
1754                  '\x9b' : ('rsaquo', '203A'),
1755                  '\x9c' : ('oelig', '153'),
1756                  '\x9d' : '?',
1757                  '\x9e' : ('#x17E', '17E'),
1758                  '\x9f' : ('Yuml', ''),}
1759
1760 #######################################################################
1761
1762
1763 #By default, act as an HTML pretty-printer.
1764 if __name__ == '__main__':
1765     import sys
1766     soup = BeautifulSoup(sys.stdin.read())
1767     print soup.prettify()