Initial revision
[blender.git] / intern / python / modules / TextTools / TextTools.py
1 """ mxTextTools - A tools package for fast text processing.
2
3     (c) Copyright Marc-Andre Lemburg; All Rights Reserved.
4     See the documentation for further information on copyrights,
5     or contact the author (mal@lemburg.com).
6 """
7 import string,types
8
9 #
10 # import the C module and the version number
11 #
12 from mxTextTools import *
13 from mxTextTools import __version__
14
15 #
16 # import the symbols needed to write tag tables
17 #
18 from Constants.TagTables import *
19
20 #
21 # import the some handy character sets
22 #
23 from Constants.Sets import *
24
25 #
26 # format and print tables, taglists and joinlists:
27 #
28 def format_entry(table,i,
29
30                  TupleType=types.TupleType):
31
32     """ Returns a pp-formatted tag table entry as string 
33     """
34     e = table[i]
35     jne = 0
36     je = 1
37     t,c,m = e[:3]
38     if len(e)>3: jne = e[3]
39     if len(e)>4: je = e[4]
40     flags,cmd = divmod(c,256)
41     c = id2cmd[cmd]
42     if type(m) == TupleType and c in ('Table','SubTable'):
43         m = '<table>'
44     elif m == None:
45         m = 'Here/To'
46     else:
47         m = repr(m)
48         if len(m) > 17:
49             m = m[:17]+'...'
50     return '%-15.15s : %-30s : jne=%+i : je=%+i' % \
51            (repr(t),'%-.15s : %s'%(c,m),jne,je)
52
53 def format_table(table,i=-1):
54     
55     """ Returns a pp-formatted version of the tag table as string """
56
57     l = []
58     for j in range(len(table)):
59         if i == j:
60             l.append('--> '+format_entry(table,j))
61         else:
62             l.append('    '+format_entry(table,j))
63     return string.join(l,'\n')+'\n'
64
65 def print_tagtable(table):
66
67     """ Print the tag table 
68     """
69     print format_table(table)
70
71 def print_tags(text,tags,indent=0):
72
73     """ Print the taglist tags for text using the given indent level 
74     """
75     for tag,l,r,subtags in tags:
76         tagname = repr(tag)
77         if len(tagname) > 20:
78             tagname = tagname[:20] + '...'
79         target = repr(text[l:r])
80         if len(target) > 60:
81             target = target[:60] + '...'
82         if subtags == None:
83             print ' '+indent*' |',tagname,': ',target,(l,r)
84         else:
85             print ' '+indent*' |',tagname,': ',target,(l,r)
86             print_tags(text,subtags,indent+1)
87
88 def print_joinlist(joins,indent=0,
89                    
90                    StringType=types.StringType):
91
92     """ Print the joinlist joins using the given indent level 
93     """
94     for j in joins:
95         if type(j) == StringType:
96             text = repr(j)
97             if len(text) > 40:
98                 text = text[:40] + '...'
99             print ' '+indent*' |',text,' (len = %i)' % len(j)
100         else:
101             text = j[0]
102             l,r = j[1:3]
103             text = repr(text[l:r])
104             if len(text) > 40:
105                 text = text[:40] + '...'
106             print ' '+indent*' |',text,' (len = %i)' % (r-l),(l,r)
107
108 def normlist(jlist,
109                    
110              StringType=types.StringType):
111
112     """ Return a normalized joinlist.
113
114         All tuples in the joinlist are turned into real strings.  The
115         resulting list is a equivalent copy of the joinlist only
116         consisting of strings.
117         
118     """
119     l = [''] * len(jlist)
120     for i in range(len(jlist)):
121         entry = jlist[i]
122         if type(entry) == StringType:
123             l[i] = entry
124         else:
125             l[i] = entry[0][entry[1]:entry[2]]
126     return l
127
128 #
129 # aid for matching from a list of words
130 #
131 def _lookup_dict(l,index=0):
132     
133     d = {}
134     for w in l:
135         c = w[index]
136         if d.has_key(c):
137             d[c].append(w)
138         else:
139             d[c] = [w]
140     return d
141
142 def word_in_list(l):
143
144     """ Creates a lookup table that matches the words in l 
145     """
146     t = []
147     d = _lookup_dict(l)
148     keys = d.keys()
149     if len(keys) < 18: # somewhat arbitrary bound
150         # fast hint for small sets
151         t.append((None,IsIn,string.join(d.keys(),'')))
152         t.append((None,Skip,-1))
153     # test groups
154     for c, group in d.items():
155         t.append(None) # hint will be filled in later
156         i = len(t)-1
157         for w in group:
158             t.append((None,Word,w[1:],+1,MatchOk))
159         t.append((None,Fail,Here))
160         # add hint
161         t[i] = (None,Is,c,len(t)-i)
162     t.append((None,Fail,Here))
163     return tuple(t)
164
165 #
166 # Extra stuff useful in combination with the C functions
167 #
168
169 def replace(text,what,with,start=0,stop=None,
170
171             SearchObject=BMS,join=join,joinlist=joinlist,tag=tag,
172             string_replace=string.replace,type=type,
173             StringType=types.StringType):
174
175     """A fast replacement for string.replace.
176     
177        what can be given as string or search object.
178
179        This function is a good example for the AppendTagobj-flag usage
180        (the taglist can be used directly as joinlist).
181        
182     """
183     if type(what) == StringType:
184         so = SearchObject(what)
185     else:
186         so = what
187         what = so.match
188     if stop is None:
189         if start == 0 and len(what) < 2:
190             return string_replace(text,what,with)
191         stop = len(text)
192     t = ((text,sWordStart,so,+2),
193          # Found something, replace and continue searching
194          (with,Skip+AppendTagobj,len(what),-1,-1),
195          # Rest of text
196          (text,Move,ToEOF)
197          )
198     found,taglist,last = tag(text,t,start,stop)
199     if not found:
200         return text
201     return join(taglist)
202
203 # Alternative (usually slower) versions using different techniques:
204
205 def _replace2(text,what,with,start=0,stop=None,
206
207               join=join,joinlist=joinlist,tag=tag,
208               StringType=types.StringType,BMS=BMS):
209
210     """Analogon to string.replace; returns a string with all occurences
211        of what in text[start:stop] replaced by with
212        - uses a one entry tag-table and a Boyer-Moore-Search-object
213        - what can be a string or a BMS/FS search object
214        - it's faster than string.replace in those cases, where
215          the what-string gets long and/or many replacements are found;
216          faster meaning from a few percent up to many times as fast
217        - start and stop define the slice of text to work in
218        - stop defaults to len(text)
219     """
220     if stop is None:
221         stop = len(text)
222     if type(what) == StringType:
223         what=BMS(what)
224     t = ((with,sFindWord,what,+1,+0),)
225     found,taglist,last = tag(text,t,start,stop)
226     if not found: 
227         return text
228     return join(joinlist(text,taglist))
229
230 def _replace3(text,what,with,
231
232               join=string.join,FS=FS,
233               StringType=types.StringType):
234
235     if type(what) == StringType:
236         what=FS(what)
237     slices = what.findall(text)
238     if not slices:
239         return text
240     l = []
241     x = 0
242     for left,right in slices:
243         l.append(text[x:left] + with)
244         x = right
245     l.append(text[x:])
246     return join(l,'')
247
248 def _replace4(text,what,with,
249
250               join=join,joinlist=joinlist,tag=tag,FS=FS,
251               StringType=types.StringType):
252
253     if type(what) == StringType:
254         what=FS(what)
255     slices = what.findall(text)
256     if not slices:
257         return text
258     repl = [None]*len(slices)
259     for i in range(len(slices)):
260         repl[i] = (with,)+slices[i]
261     return join(joinlist(text,repl))
262
263
264 def find(text,what,start=0,stop=None,
265
266          SearchObject=FS):
267
268     """ A faster replacement for string.find().
269
270         Uses a search object for the task. Returns the position of the
271         first occurance of what in text[start:stop]. stop defaults to
272         len(text).  Returns -1 in case no occurance was found.
273         
274     """
275     if stop:
276         return SearchObject(what).find(text,start,stop)
277     else:
278         return SearchObject(what).find(text,start)
279
280 def findall(text,what,start=0,stop=None,
281
282             SearchObject=FS):
283
284     """ Find all occurances of what in text.
285
286         Uses a search object for the task. Returns a list of slice
287         tuples (l,r) marking the all occurances in
288         text[start:stop]. stop defaults to len(text).  Returns an
289         empty list in case no occurance was found.
290         
291     """
292     if stop:
293         return SearchObject(what).findall(text,start,stop)
294     else:
295         return SearchObject(what).findall(text,start)
296
297 def split(text,sep,start=0,stop=None,translate=None,
298
299           SearchObject=FS):
300
301     """ A faster replacement for string.split().
302
303         Uses a search object for the task. Returns the result of
304         cutting the text[start:stop] string into snippets at every sep
305         occurance in form of a list of substrings. translate is passed
306         to the search object as translation string.
307
308         XXX convert to a C function... or even better, add as method
309         to search objects.
310
311     """
312     if translate:
313         so = SearchObject(sep,translate)
314     else:
315         so = SearchObject(sep)
316     if stop:
317         cuts = so.findall(text,start,stop)
318     else:
319         cuts = so.findall(text,start)
320     l = 0
321     list = []
322     append = list.append
323     for left,right in cuts:
324         append(text[l:left])
325         l = right
326     append(text[l:])
327     return list
328
329 # helper for tagdict
330 def _tagdict(text,dict,prefix,taglist):
331
332     for o,l,r,s in taglist:
333         pfx = prefix + str(o)
334         dict[pfx] = text[l:r]
335         if s:
336             _tagdict(text,dict,pfx+'.',s)
337
338 def tagdict(text,*args):
339
340     """ Tag a text just like the function tag() and then convert
341         its output into a dictionary where the tagobjects reference
342         their respective strings
343         - this function emulates the interface of tag()
344         - in contrast to tag() this funtion *does* make copies
345           of the found stings
346         - returns a tuple (rc,tagdict,next) with the same meaning
347           of rc and next as tag(); tagdict is the new dictionary - 
348           None in case rc is 0
349     """
350     rc,taglist,next = apply(tag,(text,)+args)
351     if not rc:
352         return (rc,None,next)
353     d = {}
354     tagdict = _tagdict
355     for o,l,r,s in taglist:
356         pfx = str(o)
357         d[pfx] = text[l:r]
358         if s:
359             tagdict(text,dict,pfx+'.',s)
360     return (rc,d,next)
361
362 def invset(chars):
363     
364     """ Return a set with all characters *except* the ones in chars.
365     """
366     return set(chars,0)
367
368 def is_whitespace(text,start=0,stop=None,
369
370                   nonwhitespace=nonwhitespace_set,setfind=setfind):
371
372     """ Return 1 iff text[start:stop] only contains whitespace
373         characters (as defined in Constants/Sets.py), 0 otherwise.
374     """
375     if stop is None:
376         stop = len(text)
377     i = setfind(text,nonwhitespace,start,stop)
378     return (i < 0)
379
380 def collapse(text,seperator=' ',
381
382              join=join,setsplit=setsplit,collapse_set=set(newline+whitespace)):
383
384     """ Eliminates newline characters and compresses whitespace
385         characters into one space.
386
387         The result is a one line text string. Tim Peters will like
388         this function called with '-' seperator ;-)
389         
390     """
391     return join(setsplit(text,collapse_set),seperator)
392
393 _linesplit_table = (
394     (None,Is,'\r',+1),
395     (None,Is,'\n',+1),
396     ('line',AllInSet+AppendMatch,set('\r\n',0),+1,-2),
397     (None,EOF,Here,+1,MatchOk),
398     ('empty line',Skip+AppendMatch,0,0,-4),
399     )
400
401 def splitlines(text,
402
403                tag=tag,linesplit_table=_linesplit_table):
404
405     """ Split text into a list of single lines.
406
407         The following combinations are considered to be line-ends:
408         '\r', '\r\n', '\n'; they may be used in any combination.  The
409         line-end indicators are removed from the strings prior to
410         adding them to the list.
411
412         This function allows dealing with text files from Macs, PCs
413         and Unix origins in a portable way.
414         
415     """
416     return tag(text,linesplit_table)[1]
417
418 _linecount_table = (
419     (None,Is,'\r',+1),
420     (None,Is,'\n',+1),
421     ('line',AllInSet+AppendTagobj,set('\r\n',0),+1,-2),
422     (None,EOF,Here,+1,MatchOk),
423     ('empty line',Skip+AppendTagobj,0,0,-4),
424     )
425
426 def countlines(text,
427
428                linecount_table=_linecount_table):
429
430     """ Returns the number of lines in text.
431
432         Line ends are treated just like for splitlines() in a
433         portable way.
434     """
435     return len(tag(text,linecount_table)[1])
436
437 _wordsplit_table = (
438     (None,AllInSet,whitespace_set,+1),
439     ('word',AllInSet+AppendMatch,nonwhitespace_set,+1,-1),
440     (None,EOF,Here,+1,MatchOk),
441     )
442
443 def splitwords(text,
444
445                setsplit=setsplit,whitespace_set=whitespace_set):
446
447     """ Split text into a list of single words.
448
449         Words are separated by whitespace. The whitespace is stripped
450         before adding the words to the list.
451         
452     """
453     return setsplit(text,whitespace_set)
454
455 #
456 # Testing and benchmarking
457 #
458
459 # Taken from my hack.py module:
460 import time
461 class _timer:
462
463     """ timer class with a quite obvious interface
464         - .start() starts a fairly accurate CPU-time timer plus an
465           absolute timer
466         - .stop() stops the timer and returns a tuple: the CPU-time in seconds
467           and the absolute time elapsed since .start() was called
468     """
469
470     utime = 0
471     atime = 0
472
473     def start(self,
474               clock=time.clock,time=time.time):
475         self.atime = time()
476         self.utime = clock()
477
478     def stop(self,
479              clock=time.clock,time=time.time):
480         self.utime = clock() - self.utime
481         self.atime = time() - self.atime
482         return self.utime,self.atime
483
484     def usertime(self,
485                  clock=time.clock,time=time.time):
486         self.utime = clock() - self.utime
487         self.atime = time() - self.atime
488         return self.utime
489
490     def abstime(self,
491                 clock=time.clock,time=time.time):
492         self.utime = clock() - self.utime
493         self.atime = time() - self.atime
494         return self.utime
495
496     def __str__(self):
497
498         return '%0.2fu %0.2fa sec.' % (self.utime,self.atime)
499
500 def _bench(file='mxTextTools/mxTextTools.c'):
501
502     def mismatch(orig,new):
503         print
504         for i in range(len(orig)):
505             if orig[i] != new[i]:
506                 break
507         else:
508             print 'Length mismatch: orig=%i new=%i' % (len(orig),len(new))
509             if len(orig) > len(new):
510                 print 'Missing chars:'+repr(orig[len(new):])
511             else:
512                 print 'Excess chars:'+repr(new[len(orig):])
513             print
514             return
515         print 'Mismatch at offset %i:' % i
516         print (orig[i-100:i] 
517                + '<- %s != %s ->' % (repr(orig[i]),repr(new[i]))
518                + orig[i+1:i+100])
519         print
520         
521     text = open(file).read()
522     import string
523
524     t = _timer()
525     print 'Working on a %i byte string' % len(text)
526
527     if 0:
528         print
529         print 'Replacing strings'
530         print '-'*72
531         print
532         for what,with in (('m','M'),('mx','MX'),('mxText','MXTEXT'),
533                           ('hmm','HMM'),('hmmm','HMM'),('hmhmm','HMM')):
534             print 'Replace "%s" with "%s"' % (what,with)
535             t.start()
536             for i in range(100):
537                 rtext = string.replace(text,what,with)
538             print 'with string.replace:',t.stop(),'sec.'
539             t.start()
540             for i in range(100):
541                 ttext = replace(text,what,with)
542             print 'with tag.replace:',t.stop(),'sec.'
543             if ttext != rtext:
544                 print 'results are NOT ok !'
545                 print '-'*72
546                 mismatch(rtext,ttext)
547             t.start()
548             for i in range(100):
549                 ttext = _replace2(text,what,with)
550             print 'with tag._replace2:',t.stop(),'sec.'
551             if ttext != rtext:
552                 print 'results are NOT ok !'
553                 print '-'*72
554                 print rtext
555             t.start()
556             for i in range(100):
557                 ttext = _replace3(text,what,with)
558             print 'with tag._replace3:',t.stop(),'sec.'
559             if ttext != rtext:
560                 print 'results are NOT ok !'
561                 print '-'*72
562                 print rtext
563             t.start()
564             for i in range(100):
565                 ttext = _replace4(text,what,with)
566             print 'with tag._replace4:',t.stop(),'sec.'
567             if ttext != rtext:
568                 print 'results are NOT ok !'
569                 print '-'*72
570                 print rtext
571             print
572
573     if 0:
574         print
575         print 'String lower/upper'
576         print '-'*72
577         print
578
579         op = string.lower
580         t.start()
581         for i in range(1000):
582             op(text)
583         t.stop()
584         print ' string.lower:',t
585
586         op = string.upper
587         t.start()
588         for i in range(1000):
589             op(text)
590         t.stop()
591         print ' string.upper:',t
592
593         op = upper
594         t.start()
595         for i in range(1000):
596             op(text)
597         t.stop()
598         print ' TextTools.upper:',t
599
600         op = lower
601         t.start()
602         for i in range(1000):
603             op(text)
604         t.stop()
605         print ' TextTools.lower:',t
606
607         print 'Testing...',
608         ltext = string.lower(text)
609         assert ltext == lower(text)
610         utext = string.upper(text)
611         assert utext == upper(text)
612         print 'ok.'
613
614     if 0:
615         print
616         print 'Joining lists'
617         print '-'*72
618         print
619
620         l = setsplit(text,whitespace_set)
621
622         op = string.join
623         t.start()
624         for i in range(1000):
625             op(l)
626         t.stop()
627         print ' string.join:',t
628
629         op = join
630         t.start()
631         for i in range(1000):
632             op(l)
633         t.stop()
634         print ' TextTools.join:',t
635
636         op = string.join
637         t.start()
638         for i in range(1000):
639             op(l,' ')
640         t.stop()
641         print ' string.join with seperator:',t
642
643         op = join
644         t.start()
645         for i in range(1000):
646             op(l,' ')
647         t.stop()
648         print ' TextTools.join with seperator:',t
649
650     if 0:
651         print
652         print 'Creating join lists'
653         print '-'*72
654         print
655
656         repl = []
657         for i in range(0,len(text),10):
658             repl.append(str(i),i,i+1)
659
660         op = joinlist
661         t.start()
662         for i in range(1000):
663             op(text,repl)
664         t.stop()
665         print ' TextTools.joinlist:',t
666
667     if 0:
668         print
669         print 'Splitting text'
670         print '-'*72
671         print
672
673         op = string.split
674         t.start()
675         for i in range(100):
676             op(text)
677         t.stop()
678         print ' string.split whitespace:',t,'(',len(op(text)),'snippets )'
679
680         op = setsplit
681         ws = whitespace_set
682         t.start()
683         for i in range(100):
684             op(text,ws)
685         t.stop()
686         print ' TextTools.setsplit whitespace:',t,'(',len(op(text,ws)),'snippets )'
687
688         assert string.split(text) == setsplit(text,ws)
689
690         op = string.split
691         sep = 'a'
692         t.start()
693         for i in range(100):
694             op(text,sep)
695         t.stop()
696         print ' string.split at "a":',t,'(',len(op(text,sep)),'snippets )'
697
698         op = split
699         sep = 'a'
700         t.start()
701         for i in range(100):
702             op(text,sep)
703         t.stop()
704         print ' TextTools.split at "a":',t,'(',len(op(text,sep)),'snippets )'
705
706         op = charsplit
707         sep = 'a'
708         t.start()
709         for i in range(100):
710             op(text,sep)
711         t.stop()
712         print ' TextTools.charsplit at "a":',t,'(',len(op(text,sep)),'snippets )'
713
714         op = setsplit
715         sep = set('a')
716         t.start()
717         for i in range(100):
718             op(text,sep)
719         t.stop()
720         print ' TextTools.setsplit at "a":',t,'(',len(op(text,sep)),'snippets )'
721
722         # Note: string.split and setsplit don't work identically !
723
724         op = string.split
725         sep = 'int'
726         t.start()
727         for i in range(100):
728             op(text,sep)
729         t.stop()
730         print ' string.split at "int":',t,'(',len(op(text,sep)),'snippets )'
731
732         op = split
733         sep = 'int'
734         t.start()
735         for i in range(100):
736             op(text,sep)
737         t.stop()
738         print ' TextTools.split at "int":',t,'(',len(op(text,sep)),'snippets )'
739
740         op = setsplit
741         sep = set('int')
742         t.start()
743         for i in range(100):
744             op(text,sep)
745         t.stop()
746         print ' TextTools.setsplit at "i", "n", "t":',t,'(',len(op(text,sep)),'snippets )'
747
748         op = string.split
749         sep = 'register'
750         t.start()
751         for i in range(100):
752             op(text,sep)
753         t.stop()
754         print ' string.split at "register":',t,'(',len(op(text,sep)),'snippets )'
755
756         op = split
757         sep = 'register'
758         t.start()
759         for i in range(100):
760             op(text,sep)
761         t.stop()
762         print ' TextTools.split at "register":',t,'(',len(op(text,sep)),'snippets )'
763
764 if __name__=='__main__':
765     _bench()
766