bitbake/method pool:
[bitbake.git] / lib / bb / __init__.py
1 #!/usr/bin/python
2 # ex:ts=4:sw=4:sts=4:et
3 # -*- tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
4 """
5 BitBake Build System Python Library
6
7 Copyright (C) 2003  Holger Schurig
8 Copyright (C) 2003, 2004  Chris Larson
9
10 Based on Gentoo's portage.py.
11
12 This program is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free Software
14 Foundation; either version 2 of the License, or (at your option) any later
15 version.
16
17 This program is distributed in the hope that it will be useful, but WITHOUT
18 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc., 59 Temple
23 Place, Suite 330, Boston, MA 02111-1307 USA.
24 """
25
26 __version__ = "1.3.3.4"
27
28 __all__ = [
29
30     "debug",
31     "note",
32     "error",
33     "fatal",
34
35     "mkdirhier",
36     "movefile",
37
38     "tokenize",
39     "evaluate",
40     "flatten",
41     "relparse",
42     "ververify",
43     "isjustname",
44     "isspecific",
45     "pkgsplit",
46     "catpkgsplit",
47     "vercmp",
48     "pkgcmp",
49     "dep_parenreduce",
50     "dep_opconvert",
51     "digraph",
52
53 # fetch
54     "decodeurl",
55     "encodeurl",
56
57 # modules
58     "parse",
59     "data",
60     "event",
61     "build",
62     "fetch",
63     "manifest",
64     "methodpool"
65  ]
66
67 whitespace = '\t\n\x0b\x0c\r '
68 lowercase = 'abcdefghijklmnopqrstuvwxyz'
69
70 import sys, os, types, re, string
71
72 #projectdir = os.path.dirname(os.path.dirname(os.path.abspath(sys.argv[0])))
73 projectdir = os.getcwd()
74
75 debug_level = 0
76
77 if "BBDEBUG" in os.environ:
78     level = int(os.environ["BBDEBUG"])
79     if level:
80         debug_level = level
81     else:
82         debug_level = 0
83
84 class VarExpandError(Exception):
85     pass
86
87 class MalformedUrl(Exception):
88     """Exception raised when encountering an invalid url"""
89
90
91 #######################################################################
92 #######################################################################
93 #
94 # SECTION: Debug
95 #
96 # PURPOSE: little functions to make yourself known
97 #
98 #######################################################################
99 #######################################################################
100
101 debug_prepend = ''
102
103
104 def debug(lvl, *args):
105     if debug_level >= lvl:
106         print debug_prepend + 'DEBUG:', ''.join(args)
107
108 def note(*args):
109     print debug_prepend + 'NOTE:', ''.join(args)
110
111 def error(*args):
112     print debug_prepend + 'ERROR:', ''.join(args)
113
114 def fatal(*args):
115     print debug_prepend + 'ERROR:', ''.join(args)
116     sys.exit(1)
117
118
119 #######################################################################
120 #######################################################################
121 #
122 # SECTION: File
123 #
124 # PURPOSE: Basic file and directory tree related functions
125 #
126 #######################################################################
127 #######################################################################
128
129 def mkdirhier(dir):
130     """Create a directory like 'mkdir -p', but does not complain if
131     directory already exists like os.makedirs
132     """
133
134     debug(3, "mkdirhier(%s)" % dir)
135     try:
136         os.makedirs(dir)
137         debug(2, "created " + dir)
138     except OSError, e:
139         if e.errno != 17: raise e
140
141
142 #######################################################################
143
144 import stat
145
146 def movefile(src,dest,newmtime=None,sstat=None):
147     """Moves a file from src to dest, preserving all permissions and
148     attributes; mtime will be preserved even when moving across
149     filesystems.  Returns true on success and false on failure. Move is
150     atomic.
151     """
152
153     #print "movefile("+src+","+dest+","+str(newmtime)+","+str(sstat)+")"
154     try:
155         if not sstat:
156             sstat=os.lstat(src)
157     except Exception, e:
158         print "!!! Stating source file failed... movefile()"
159         print "!!!",e
160         return None
161
162     destexists=1
163     try:
164         dstat=os.lstat(dest)
165     except:
166         dstat=os.lstat(os.path.dirname(dest))
167         destexists=0
168
169     if destexists:
170         if stat.S_ISLNK(dstat[stat.ST_MODE]):
171             try:
172                 os.unlink(dest)
173                 destexists=0
174             except Exception, e:
175                 pass
176
177     if stat.S_ISLNK(sstat[stat.ST_MODE]):
178         try:
179             target=os.readlink(src)
180             if destexists and not stat.S_ISDIR(dstat[stat.ST_MODE]):
181                 os.unlink(dest)
182             os.symlink(target,dest)
183 #            os.lchown(dest,sstat[stat.ST_UID],sstat[stat.ST_GID])
184             os.unlink(src)
185             return os.lstat(dest)
186         except Exception, e:
187             print "!!! failed to properly create symlink:"
188             print "!!!",dest,"->",target
189             print "!!!",e
190             return None
191
192     renamefailed=1
193     if sstat[stat.ST_DEV]==dstat[stat.ST_DEV]:
194         try:
195             ret=os.rename(src,dest)
196             renamefailed=0
197         except Exception, e:
198             import errno
199             if e[0]!=errno.EXDEV:
200                 # Some random error.
201                 print "!!! Failed to move",src,"to",dest
202                 print "!!!",e
203                 return None
204             # Invalid cross-device-link 'bind' mounted or actually Cross-Device
205
206     if renamefailed:
207         didcopy=0
208         if stat.S_ISREG(sstat[stat.ST_MODE]):
209             try: # For safety copy then move it over.
210                 shutil.copyfile(src,dest+"#new")
211                 os.rename(dest+"#new",dest)
212                 didcopy=1
213             except Exception, e:
214                 print '!!! copy',src,'->',dest,'failed.'
215                 print "!!!",e
216                 return None
217         else:
218             #we don't yet handle special, so we need to fall back to /bin/mv
219             a=getstatusoutput("/bin/mv -f "+"'"+src+"' '"+dest+"'")
220             if a[0]!=0:
221                 print "!!! Failed to move special file:"
222                 print "!!! '"+src+"' to '"+dest+"'"
223                 print "!!!",a
224                 return None # failure
225         try:
226             if didcopy:
227                 missingos.lchown(dest,sstat[stat.ST_UID],sstat[stat.ST_GID])
228                 os.chmod(dest, stat.S_IMODE(sstat[stat.ST_MODE])) # Sticky is reset on chown
229                 os.unlink(src)
230         except Exception, e:
231             print "!!! Failed to chown/chmod/unlink in movefile()"
232             print "!!!",dest
233             print "!!!",e
234             return None
235
236     if newmtime:
237         os.utime(dest,(newmtime,newmtime))
238     else:
239         os.utime(dest, (sstat[stat.ST_ATIME], sstat[stat.ST_MTIME]))
240         newmtime=sstat[stat.ST_MTIME]
241     return newmtime
242
243
244
245 #######################################################################
246 #######################################################################
247 #
248 # SECTION: Download
249 #
250 # PURPOSE: Download via HTTP, FTP, CVS, BITKEEPER, handling of MD5-signatures
251 #          and mirrors
252 #
253 #######################################################################
254 #######################################################################
255
256 def decodeurl(url):
257     """Decodes an URL into the tokens (scheme, network location, path,
258     user, password, parameters).
259
260     >>> decodeurl("http://www.google.com/index.html")
261     ('http', 'www.google.com', '/index.html', '', '', {})
262
263     CVS url with username, host and cvsroot. The cvs module to check out is in the
264     parameters:
265
266     >>> decodeurl("cvs://anoncvs@cvs.handhelds.org/cvs;module=familiar/dist/ipkg")
267     ('cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', '', {'module': 'familiar/dist/ipkg'})
268
269     Dito, but this time the username has a password part. And we also request a special tag
270     to check out.
271
272     >>> decodeurl("cvs://anoncvs:anonymous@cvs.handhelds.org/cvs;module=familiar/dist/ipkg;tag=V0-99-81")
273     ('cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', 'anonymous', {'tag': 'V0-99-81', 'module': 'familiar/dist/ipkg'})
274     """
275
276     m = re.compile('(?P<type>[^:]*)://((?P<user>.+)@)?(?P<location>[^;]+)(;(?P<parm>.*))?').match(url)
277     if not m:
278         raise MalformedUrl(url)
279
280     type = m.group('type')
281     location = m.group('location')
282     if not location:
283         raise MalformedUrl(url)
284     user = m.group('user')
285     parm = m.group('parm')
286     m = re.compile('(?P<host>[^/;]+)(?P<path>/[^;]+)').match(location)
287     if m:
288         host = m.group('host')
289         path = m.group('path')
290     else:
291         host = ""
292         path = location
293     if user:
294         m = re.compile('(?P<user>[^:]+)(:?(?P<pswd>.*))').match(user)
295         if m:
296             user = m.group('user')
297             pswd = m.group('pswd')
298     else:
299         user = ''
300         pswd = ''
301
302     p = {}
303     if parm:
304         for s in parm.split(';'):
305             s1,s2 = s.split('=')
306             p[s1] = s2
307
308     return (type, host, path, user, pswd, p)
309
310 #######################################################################
311
312 def encodeurl(decoded):
313     """Encodes a URL from tokens (scheme, network location, path,
314     user, password, parameters).
315
316     >>> encodeurl(['http', 'www.google.com', '/index.html', '', '', {}])
317     'http://www.google.com/index.html'
318
319     CVS with username, host and cvsroot. The cvs module to check out is in the
320     parameters:
321
322     >>> encodeurl(['cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', '', {'module': 'familiar/dist/ipkg'}])
323     'cvs://anoncvs@cvs.handhelds.org/cvs;module=familiar/dist/ipkg'
324
325     Dito, but this time the username has a password part. And we also request a special tag
326     to check out.
327
328     >>> encodeurl(['cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', 'anonymous', {'tag': 'V0-99-81', 'module': 'familiar/dist/ipkg'}])
329     'cvs://anoncvs:anonymous@cvs.handhelds.org/cvs;tag=V0-99-81;module=familiar/dist/ipkg'
330     """
331
332     (type, host, path, user, pswd, p) = decoded
333
334     if not type or not path:
335         fatal("invalid or missing parameters for url encoding")
336     url = '%s://' % type
337     if user:
338         url += "%s" % user
339         if pswd:
340             url += ":%s" % pswd
341         url += "@"
342     if host:
343         url += "%s" % host
344     url += "%s" % path
345     if p:
346         for parm in p.keys():
347             url += ";%s=%s" % (parm, p[parm])
348
349     return url
350
351 #######################################################################
352
353 def which(path, item, direction = 0):
354     """Useful function for locating a file in a PATH"""
355     found = ""
356     for p in (path or "").split(':'):
357         if os.path.exists(os.path.join(p, item)):
358             found = os.path.join(p, item)
359             if direction == 0:
360                 break
361     return found
362
363 #######################################################################
364
365
366
367
368 #######################################################################
369 #######################################################################
370 #
371 # SECTION: Dependency
372 #
373 # PURPOSE: Compare build & run dependencies
374 #
375 #######################################################################
376 #######################################################################
377
378 def tokenize(mystring):
379     """Breaks a string like 'foo? (bar) oni? (blah (blah))' into (possibly embedded) lists:
380
381     >>> tokenize("x")
382     ['x']
383     >>> tokenize("x y")
384     ['x', 'y']
385     >>> tokenize("(x y)")
386     [['x', 'y']]
387     >>> tokenize("(x y) b c")
388     [['x', 'y'], 'b', 'c']
389     >>> tokenize("foo? (bar) oni? (blah (blah))")
390     ['foo?', ['bar'], 'oni?', ['blah', ['blah']]]
391     >>> tokenize("sys-apps/linux-headers nls? (sys-devel/gettext)")
392     ['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']]
393     """
394
395     newtokens = []
396     curlist   = newtokens
397     prevlists = []
398     level     = 0
399     accum     = ""
400     for x in mystring:
401         if x=="(":
402             if accum:
403                 curlist.append(accum)
404                 accum=""
405             prevlists.append(curlist)
406             curlist=[]
407             level=level+1
408         elif x==")":
409             if accum:
410                 curlist.append(accum)
411                 accum=""
412             if level==0:
413                 print "!!! tokenizer: Unmatched left parenthesis in:\n'"+mystring+"'"
414                 return None
415             newlist=curlist
416             curlist=prevlists.pop()
417             curlist.append(newlist)
418             level=level-1
419         elif x in whitespace:
420             if accum:
421                 curlist.append(accum)
422                 accum=""
423         else:
424             accum=accum+x
425     if accum:
426         curlist.append(accum)
427     if (level!=0):
428         print "!!! tokenizer: Exiting with unterminated parenthesis in:\n'"+mystring+"'"
429         return None
430     return newtokens
431
432
433 #######################################################################
434
435 def evaluate(tokens,mydefines,allon=0):
436     """Removes tokens based on whether conditional definitions exist or not.
437     Recognizes !
438
439     >>> evaluate(['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']], {})
440     ['sys-apps/linux-headers']
441
442     Negate the flag:
443
444     >>> evaluate(['sys-apps/linux-headers', '!nls?', ['sys-devel/gettext']], {})
445     ['sys-apps/linux-headers', ['sys-devel/gettext']]
446
447     Define 'nls':
448
449     >>> evaluate(['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']], {"nls":1})
450     ['sys-apps/linux-headers', ['sys-devel/gettext']]
451
452     Turn allon on:
453
454     >>> evaluate(['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']], {}, True)
455     ['sys-apps/linux-headers', ['sys-devel/gettext']]
456     """
457
458     if tokens == None:
459         return None
460     mytokens = tokens + []        # this copies the list
461     pos = 0
462     while pos < len(mytokens):
463         if type(mytokens[pos]) == types.ListType:
464             evaluate(mytokens[pos], mydefines)
465             if not len(mytokens[pos]):
466                 del mytokens[pos]
467                 continue
468         elif mytokens[pos][-1] == "?":
469             cur = mytokens[pos][:-1]
470             del mytokens[pos]
471             if allon:
472                 if cur[0] == "!":
473                     del mytokens[pos]
474             else:
475                 if cur[0] == "!":
476                     if (cur[1:] in mydefines) and (pos < len(mytokens)):
477                         del mytokens[pos]
478                         continue
479                 elif (cur not in mydefines) and (pos < len(mytokens)):
480                     del mytokens[pos]
481                     continue
482         pos = pos + 1
483     return mytokens
484
485
486 #######################################################################
487
488 def flatten(mytokens):
489     """Converts nested arrays into a flat arrays:
490
491     >>> flatten([1,[2,3]])
492     [1, 2, 3]
493     >>> flatten(['sys-apps/linux-headers', ['sys-devel/gettext']])
494     ['sys-apps/linux-headers', 'sys-devel/gettext']
495     """
496
497     newlist=[]
498     for x in mytokens:
499         if type(x)==types.ListType:
500             newlist.extend(flatten(x))
501         else:
502             newlist.append(x)
503     return newlist
504
505
506 #######################################################################
507
508 _package_weights_ = {"pre":-2,"p":0,"alpha":-4,"beta":-3,"rc":-1}    # dicts are unordered
509 _package_ends_    = ["pre", "p", "alpha", "beta", "rc", "cvs", "bk", "HEAD" ]            # so we need ordered list
510
511 def relparse(myver):
512     """Parses the last elements of a version number into a triplet, that can
513     later be compared:
514
515     >>> relparse('1.2_pre3')
516     [1.2, -2, 3.0]
517     >>> relparse('1.2b')
518     [1.2, 98, 0]
519     >>> relparse('1.2')
520     [1.2, 0, 0]
521     """
522
523     number   = 0
524     p1       = 0
525     p2       = 0
526     mynewver = myver.split('_')
527     if len(mynewver)==2:
528         # an _package_weights_
529         number = float(mynewver[0])
530         match = 0
531         for x in _package_ends_:
532             elen = len(x)
533             if mynewver[1][:elen] == x:
534                 match = 1
535                 p1 = _package_weights_[x]
536                 try:
537                     p2 = float(mynewver[1][elen:])
538                 except:
539                     p2 = 0
540                 break
541         if not match:
542             # normal number or number with letter at end
543             divider = len(myver)-1
544             if myver[divider:] not in "1234567890":
545                 # letter at end
546                 p1 = ord(myver[divider:])
547                 number = float(myver[0:divider])
548             else:
549                 number = float(myver)
550     else:
551         # normal number or number with letter at end
552         divider = len(myver)-1
553         if myver[divider:] not in "1234567890":
554             #letter at end
555             p1     = ord(myver[divider:])
556             number = float(myver[0:divider])
557         else:
558             number = float(myver)
559     return [number,p1,p2]
560
561
562 #######################################################################
563
564 __ververify_cache__ = {}
565
566 def ververify(myorigval,silent=1):
567     """Returns 1 if given a valid version string, els 0. Valid versions are in the format
568
569     <v1>.<v2>...<vx>[a-z,_{_package_weights_}[vy]]
570
571     >>> ververify('2.4.20')
572     1
573     >>> ververify('2.4..20')        # two dots
574     0
575     >>> ververify('2.x.20')            # 'x' is not numeric
576     0
577     >>> ververify('2.4.20a')
578     1
579     >>> ververify('2.4.20cvs')        # only one trailing letter
580     0
581     >>> ververify('1a')
582     1
583     >>> ververify('test_a')            # no version at all
584     0
585     >>> ververify('2.4.20_beta1')
586     1
587     >>> ververify('2.4.20_beta')
588     1
589     >>> ververify('2.4.20_wrongext')    # _wrongext is no valid trailer
590     0
591     """
592
593     # Lookup the cache first
594     try:
595         return __ververify_cache__[myorigval]
596     except KeyError:
597         pass
598
599     if len(myorigval) == 0:
600         if not silent:
601             error("package version is empty")
602         __ververify_cache__[myorigval] = 0
603         return 0
604     myval = myorigval.split('.')
605     if len(myval)==0:
606         if not silent:
607             error("package name has empty version string")
608         __ververify_cache__[myorigval] = 0
609         return 0
610     # all but the last version must be a numeric
611     for x in myval[:-1]:
612         if not len(x):
613             if not silent:
614                 error("package version has two points in a row")
615             __ververify_cache__[myorigval] = 0
616             return 0
617         try:
618             foo = int(x)
619         except:
620             if not silent:
621                 error("package version contains non-numeric '"+x+"'")
622             __ververify_cache__[myorigval] = 0
623             return 0
624     if not len(myval[-1]):
625             if not silent:
626                 error("package version has trailing dot")
627             __ververify_cache__[myorigval] = 0
628             return 0
629     try:
630         foo = int(myval[-1])
631         __ververify_cache__[myorigval] = 1
632         return 1
633     except:
634         pass
635
636     # ok, our last component is not a plain number or blank, let's continue
637     if myval[-1][-1] in lowercase:
638         try:
639             foo = int(myval[-1][:-1])
640             return 1
641             __ververify_cache__[myorigval] = 1
642             # 1a, 2.0b, etc.
643         except:
644             pass
645     # ok, maybe we have a 1_alpha or 1_beta2; let's see
646     ep=string.split(myval[-1],"_")
647     if len(ep)!= 2:
648         if not silent:
649             error("package version has more than one letter at then end")
650         __ververify_cache__[myorigval] = 0
651         return 0
652     try:
653         foo = string.atoi(ep[0])
654     except:
655         # this needs to be numeric, i.e. the "1" in "1_alpha"
656         if not silent:
657             error("package version must have numeric part before the '_'")
658         __ververify_cache__[myorigval] = 0
659         return 0
660
661     for mye in _package_ends_:
662         if ep[1][0:len(mye)] == mye:
663             if len(mye) == len(ep[1]):
664                 # no trailing numeric is ok
665                 __ververify_cache__[myorigval] = 1
666                 return 1
667             else:
668                 try:
669                     foo = string.atoi(ep[1][len(mye):])
670                     __ververify_cache__[myorigval] = 1
671                     return 1
672                 except:
673                     # if no _package_weights_ work, *then* we return 0
674                     pass
675     if not silent:
676         error("package version extension after '_' is invalid")
677     __ververify_cache__[myorigval] = 0
678     return 0
679
680
681 def isjustname(mypkg):
682     myparts = string.split(mypkg,'-')
683     for x in myparts:
684         if ververify(x):
685             return 0
686     return 1
687
688
689 _isspecific_cache_={}
690
691 def isspecific(mypkg):
692     "now supports packages with no category"
693     try:
694         return __isspecific_cache__[mypkg]
695     except:
696         pass
697
698     mysplit = string.split(mypkg,"/")
699     if not isjustname(mysplit[-1]):
700             __isspecific_cache__[mypkg] = 1
701             return 1
702     __isspecific_cache__[mypkg] = 0
703     return 0
704
705
706 #######################################################################
707
708 __pkgsplit_cache__={}
709
710 def pkgsplit(mypkg, silent=1):
711
712     """This function can be used as a package verification function. If
713     it is a valid name, pkgsplit will return a list containing:
714     [pkgname, pkgversion(norev), pkgrev ].
715
716     >>> pkgsplit('')
717     >>> pkgsplit('x')
718     >>> pkgsplit('x-')
719     >>> pkgsplit('-1')
720     >>> pkgsplit('glibc-1.2-8.9-r7')
721     >>> pkgsplit('glibc-2.2.5-r7')
722     ['glibc', '2.2.5', 'r7']
723     >>> pkgsplit('foo-1.2-1')
724     >>> pkgsplit('Mesa-3.0')
725     ['Mesa', '3.0', 'r0']
726     """
727
728     try:
729         return __pkgsplit_cache__[mypkg]
730     except KeyError:
731         pass
732
733     myparts = string.split(mypkg,'-')
734     if len(myparts) < 2:
735         if not silent:
736             error("package name without name or version part")
737         __pkgsplit_cache__[mypkg] = None
738         return None
739     for x in myparts:
740         if len(x) == 0:
741             if not silent:
742                 error("package name with empty name or version part")
743             __pkgsplit_cache__[mypkg] = None
744             return None
745     # verify rev
746     revok = 0
747     myrev = myparts[-1]
748     ververify(myrev, silent)
749     if len(myrev) and myrev[0] == "r":
750         try:
751             string.atoi(myrev[1:])
752             revok = 1
753         except:
754             pass
755     if revok:
756         if ververify(myparts[-2]):
757             if len(myparts) == 2:
758                 __pkgsplit_cache__[mypkg] = None
759                 return None
760             else:
761                 for x in myparts[:-2]:
762                     if ververify(x):
763                         __pkgsplit_cache__[mypkg]=None
764                         return None
765                         # names can't have versiony looking parts
766                 myval=[string.join(myparts[:-2],"-"),myparts[-2],myparts[-1]]
767                 __pkgsplit_cache__[mypkg]=myval
768                 return myval
769         else:
770             __pkgsplit_cache__[mypkg] = None
771             return None
772
773     elif ververify(myparts[-1],silent):
774         if len(myparts)==1:
775             if not silent:
776                 print "!!! Name error in",mypkg+": missing name part."
777             __pkgsplit_cache__[mypkg]=None
778             return None
779         else:
780             for x in myparts[:-1]:
781                 if ververify(x):
782                     if not silent: error("package name has multiple version parts")
783                     __pkgsplit_cache__[mypkg] = None
784                     return None
785             myval = [string.join(myparts[:-1],"-"), myparts[-1],"r0"]
786             __pkgsplit_cache__[mypkg] = myval
787             return myval
788     else:
789         __pkgsplit_cache__[mypkg] = None
790         return None
791
792
793 #######################################################################
794
795 __catpkgsplit_cache__ = {}
796
797 def catpkgsplit(mydata,silent=1):
798     """returns [cat, pkgname, version, rev ]
799
800     >>> catpkgsplit('sys-libs/glibc-1.2-r7')
801     ['sys-libs', 'glibc', '1.2', 'r7']
802     >>> catpkgsplit('glibc-1.2-r7')
803     [None, 'glibc', '1.2', 'r7']
804     """
805
806     try:
807         return __catpkgsplit_cache__[mydata]
808     except KeyError:
809         pass
810
811     cat = os.path.basename(os.path.dirname(mydata))
812     mydata = os.path.join(cat, os.path.basename(mydata))
813     if mydata[-3:] == '.bb':
814         mydata = mydata[:-3]
815
816     mysplit = mydata.split("/")
817     p_split = None
818     splitlen = len(mysplit)
819     if splitlen == 1:
820         retval = [None]
821         p_split = pkgsplit(mydata,silent)
822     else:
823         retval = [mysplit[splitlen - 2]]
824         p_split = pkgsplit(mysplit[splitlen - 1],silent)
825     if not p_split:
826         __catpkgsplit_cache__[mydata] = None
827         return None
828     retval.extend(p_split)
829     __catpkgsplit_cache__[mydata] = retval
830     return retval
831
832
833 #######################################################################
834
835 __vercmp_cache__ = {}
836
837 def vercmp(val1,val2):
838     """This takes two version strings and returns an integer to tell you whether
839     the versions are the same, val1>val2 or val2>val1.
840
841     >>> vercmp('1', '2')
842     -1.0
843     >>> vercmp('2', '1')
844     1.0
845     >>> vercmp('1', '1.0')
846     0
847     >>> vercmp('1', '1.1')
848     -1.0
849     >>> vercmp('1.1', '1_p2')
850     1.0
851     """
852
853     # quick short-circuit
854     if val1 == val2:
855         return 0
856     valkey = val1+" "+val2
857
858     # cache lookup
859     try:
860         return __vercmp_cache__[valkey]
861         try:
862             return - __vercmp_cache__[val2+" "+val1]
863         except KeyError:
864             pass
865     except KeyError:
866         pass
867
868     # consider 1_p2 vc 1.1
869     # after expansion will become (1_p2,0) vc (1,1)
870     # then 1_p2 is compared with 1 before 0 is compared with 1
871     # to solve the bug we need to convert it to (1,0_p2)
872     # by splitting _prepart part and adding it back _after_expansion
873
874     val1_prepart = val2_prepart = ''
875     if val1.count('_'):
876         val1, val1_prepart = val1.split('_', 1)
877     if val2.count('_'):
878         val2, val2_prepart = val2.split('_', 1)
879
880     # replace '-' by '.'
881     # FIXME: Is it needed? can val1/2 contain '-'?
882
883     val1 = string.split(val1,'-')
884     if len(val1) == 2:
885         val1[0] = val1[0] +"."+ val1[1]
886     val2 = string.split(val2,'-')
887     if len(val2) == 2:
888         val2[0] = val2[0] +"."+ val2[1]
889
890     val1 = string.split(val1[0],'.')
891     val2 = string.split(val2[0],'.')
892
893     # add back decimal point so that .03 does not become "3" !
894     for x in range(1,len(val1)):
895         if val1[x][0] == '0' :
896             val1[x] = '.' + val1[x]
897     for x in range(1,len(val2)):
898         if val2[x][0] == '0' :
899             val2[x] = '.' + val2[x]
900
901     # extend varion numbers
902     if len(val2) < len(val1):
903         val2.extend(["0"]*(len(val1)-len(val2)))
904     elif len(val1) < len(val2):
905         val1.extend(["0"]*(len(val2)-len(val1)))
906
907     # add back _prepart tails
908     if val1_prepart:
909         val1[-1] += '_' + val1_prepart
910     if val2_prepart:
911         val2[-1] += '_' + val2_prepart
912     # The above code will extend version numbers out so they
913     # have the same number of digits.
914     for x in range(0,len(val1)):
915         cmp1 = relparse(val1[x])
916         cmp2 = relparse(val2[x])
917         for y in range(0,3):
918             myret = cmp1[y] - cmp2[y]
919             if myret != 0:
920                 __vercmp_cache__[valkey] = myret
921                 return myret
922     __vercmp_cache__[valkey] = 0
923     return 0
924
925
926 #######################################################################
927
928 def pkgcmp(pkg1,pkg2):
929     """ Compares two packages, which should have been split via
930     pkgsplit(). if the return value val is less than zero, then pkg2 is
931     newer than pkg1, zero if equal and positive if older.
932
933     >>> pkgcmp(['glibc', '2.2.5', 'r7'], ['glibc', '2.2.5', 'r7'])
934     0
935     >>> pkgcmp(['glibc', '2.2.5', 'r4'], ['glibc', '2.2.5', 'r7'])
936     -1
937     >>> pkgcmp(['glibc', '2.2.5', 'r7'], ['glibc', '2.2.5', 'r2'])
938     1
939     """
940
941     mycmp = vercmp(pkg1[1],pkg2[1])
942     if mycmp > 0:
943         return 1
944     if mycmp < 0:
945         return -1
946     r1=string.atoi(pkg1[2][1:])
947     r2=string.atoi(pkg2[2][1:])
948     if r1 > r2:
949         return 1
950     if r2 > r1:
951         return -1
952     return 0
953
954
955 #######################################################################
956
957 def dep_parenreduce(mysplit, mypos=0):
958     """Accepts a list of strings, and converts '(' and ')' surrounded items to sub-lists:
959
960     >>> dep_parenreduce([''])
961     ['']
962     >>> dep_parenreduce(['1', '2', '3'])
963     ['1', '2', '3']
964     >>> dep_parenreduce(['1', '(', '2', '3', ')', '4'])
965     ['1', ['2', '3'], '4']
966     """
967
968     while mypos < len(mysplit):
969         if mysplit[mypos] == "(":
970             firstpos = mypos
971             mypos = mypos + 1
972             while mypos < len(mysplit):
973                 if mysplit[mypos] == ")":
974                     mysplit[firstpos:mypos+1] = [mysplit[firstpos+1:mypos]]
975                     mypos = firstpos
976                     break
977                 elif mysplit[mypos] == "(":
978                     # recurse
979                     mysplit = dep_parenreduce(mysplit,mypos)
980                 mypos = mypos + 1
981         mypos = mypos + 1
982     return mysplit
983
984
985 def dep_opconvert(mysplit, myuse):
986     "Does dependency operator conversion"
987
988     mypos   = 0
989     newsplit = []
990     while mypos < len(mysplit):
991         if type(mysplit[mypos]) == types.ListType:
992             newsplit.append(dep_opconvert(mysplit[mypos],myuse))
993             mypos += 1
994         elif mysplit[mypos] == ")":
995             # mismatched paren, error
996             return None
997         elif mysplit[mypos]=="||":
998             if ((mypos+1)>=len(mysplit)) or (type(mysplit[mypos+1])!=types.ListType):
999                 # || must be followed by paren'd list
1000                 return None
1001             try:
1002                 mynew = dep_opconvert(mysplit[mypos+1],myuse)
1003             except Exception, e:
1004                 error("unable to satisfy OR dependancy: " + string.join(mysplit," || "))
1005                 raise e
1006             mynew[0:0] = ["||"]
1007             newsplit.append(mynew)
1008             mypos += 2
1009         elif mysplit[mypos][-1] == "?":
1010             # use clause, i.e "gnome? ( foo bar )"
1011             # this is a quick and dirty hack so that repoman can enable all USE vars:
1012             if (len(myuse) == 1) and (myuse[0] == "*"):
1013                 # enable it even if it's ! (for repoman) but kill it if it's
1014                 # an arch variable that isn't for this arch. XXX Sparc64?
1015                 if (mysplit[mypos][:-1] not in settings.usemask) or \
1016                         (mysplit[mypos][:-1]==settings["ARCH"]):
1017                     enabled=1
1018                 else:
1019                     enabled=0
1020             else:
1021                 if mysplit[mypos][0] == "!":
1022                     myusevar = mysplit[mypos][1:-1]
1023                     enabled = not myusevar in myuse
1024                     #if myusevar in myuse:
1025                     #    enabled = 0
1026                     #else:
1027                     #    enabled = 1
1028                 else:
1029                     myusevar=mysplit[mypos][:-1]
1030                     enabled = myusevar in myuse
1031                     #if myusevar in myuse:
1032                     #    enabled=1
1033                     #else:
1034                     #    enabled=0
1035             if (mypos +2 < len(mysplit)) and (mysplit[mypos+2] == ":"):
1036                 # colon mode
1037                 if enabled:
1038                     # choose the first option
1039                     if type(mysplit[mypos+1]) == types.ListType:
1040                         newsplit.append(dep_opconvert(mysplit[mypos+1],myuse))
1041                     else:
1042                         newsplit.append(mysplit[mypos+1])
1043                 else:
1044                     # choose the alternate option
1045                     if type(mysplit[mypos+1]) == types.ListType:
1046                         newsplit.append(dep_opconvert(mysplit[mypos+3],myuse))
1047                     else:
1048                         newsplit.append(mysplit[mypos+3])
1049                 mypos += 4
1050             else:
1051                 # normal use mode
1052                 if enabled:
1053                     if type(mysplit[mypos+1]) == types.ListType:
1054                         newsplit.append(dep_opconvert(mysplit[mypos+1],myuse))
1055                     else:
1056                         newsplit.append(mysplit[mypos+1])
1057                 # otherwise, continue
1058                 mypos += 2
1059         else:
1060             # normal item
1061             newsplit.append(mysplit[mypos])
1062             mypos += 1
1063     return newsplit
1064
1065 class digraph:
1066     """beautiful directed graph object"""
1067
1068     def __init__(self):
1069         self.dict={}
1070         #okeys = keys, in order they were added (to optimize firstzero() ordering)
1071         self.okeys=[]
1072         self.__callback_cache=[]
1073
1074     def __str__(self):
1075         str = ""
1076         for key in self.okeys:
1077             str += "%s:\t%s\n" % (key, self.dict[key][1])
1078         return str
1079
1080     def addnode(self,mykey,myparent):
1081         if not mykey in self.dict:
1082             self.okeys.append(mykey)
1083             if myparent==None:
1084                 self.dict[mykey]=[0,[]]
1085             else:
1086                 self.dict[mykey]=[0,[myparent]]
1087                 self.dict[myparent][0]=self.dict[myparent][0]+1
1088             return
1089         if myparent and (not myparent in self.dict[mykey][1]):
1090             self.dict[mykey][1].append(myparent)
1091             self.dict[myparent][0]=self.dict[myparent][0]+1
1092
1093     def delnode(self,mykey, ref = 1):
1094         """Delete a node
1095
1096         If ref is 1, remove references to this node from other nodes.
1097         If ref is 2, remove nodes that reference this node."""
1098         if not mykey in self.dict:
1099             return
1100         for x in self.dict[mykey][1]:
1101             self.dict[x][0]=self.dict[x][0]-1
1102         del self.dict[mykey]
1103         while 1:
1104             try:
1105                 self.okeys.remove(mykey)
1106             except ValueError:
1107                 break
1108         if ref:
1109             __kill = []
1110             for k in self.okeys:
1111                 if mykey in self.dict[k][1]:
1112                     if ref == 1 or ref == 2:
1113                         self.dict[k][1].remove(mykey)
1114                     if ref == 2:
1115                         __kill.append(k)
1116             for l in __kill:
1117                 self.delnode(l, ref)
1118
1119     def allnodes(self):
1120         "returns all nodes in the dictionary"
1121         return self.dict.keys()
1122
1123     def firstzero(self):
1124         "returns first node with zero references, or NULL if no such node exists"
1125         for x in self.okeys:
1126             if self.dict[x][0]==0:
1127                 return x
1128         return None
1129
1130     def firstnonzero(self):
1131         "returns first node with nonzero references, or NULL if no such node exists"
1132         for x in self.okeys:
1133             if self.dict[x][0]!=0:
1134                 return x
1135         return None
1136
1137
1138     def allzeros(self):
1139         "returns all nodes with zero references, or NULL if no such node exists"
1140         zerolist = []
1141         for x in self.dict.keys():
1142             if self.dict[x][0]==0:
1143                 zerolist.append(x)
1144         return zerolist
1145
1146     def hasallzeros(self):
1147         "returns 0/1, Are all nodes zeros? 1 : 0"
1148         zerolist = []
1149         for x in self.dict.keys():
1150             if self.dict[x][0]!=0:
1151                 return 0
1152         return 1
1153
1154     def empty(self):
1155         if len(self.dict)==0:
1156             return 1
1157         return 0
1158
1159     def hasnode(self,mynode):
1160         return mynode in self.dict
1161
1162     def getparents(self, item):
1163         if not self.hasnode(item):
1164             return []
1165         return self.dict[item][1]
1166
1167     def getchildren(self, item):
1168         if not self.hasnode(item):
1169             return []
1170         children = [i for i in self.okeys if item in self.getparents(i)]
1171         return children
1172
1173     def walkdown(self, item, callback, debug = None, usecache = False):
1174         if not self.hasnode(item):
1175             return 0
1176
1177         if usecache:
1178             if self.__callback_cache.count(item):
1179                 if debug:
1180                     print "hit cache for item: %s" % item
1181                 return 1
1182
1183         parents = self.getparents(item)
1184         children = self.getchildren(item)
1185         for p in parents:
1186             if p in children:
1187 #                print "%s is both parent and child of %s" % (p, item)
1188                 if usecache:
1189                     self.__callback_cache.append(p)
1190                 ret = callback(self, p)
1191                 if ret == 0:
1192                     return 0
1193                 continue
1194             if item == p:
1195                 print "eek, i'm my own parent!"
1196                 return 0
1197             if debug:
1198                 print "item: %s, p: %s" % (item, p)
1199             ret = self.walkdown(p, callback, debug, usecache)
1200             if ret == 0:
1201                 return 0
1202         if usecache:
1203             self.__callback_cache.append(item)
1204         return callback(self, item)
1205
1206     def walkup(self, item, callback):
1207         if not self.hasnode(item):
1208             return 0
1209
1210         parents = self.getparents(item)
1211         children = self.getchildren(item)
1212         for c in children:
1213             if c in parents:
1214                 ret = callback(self, item)
1215                 if ret == 0:
1216                     return 0
1217                 continue
1218             if item == c:
1219                 print "eek, i'm my own child!"
1220                 return 0
1221             ret = self.walkup(c, callback)
1222             if ret == 0:
1223                 return 0
1224         return callback(self, item)
1225
1226     def copy(self):
1227         mygraph=digraph()
1228         for x in self.dict.keys():
1229             mygraph.dict[x]=self.dict[x][:]
1230             mygraph.okeys=self.okeys[:]
1231         return mygraph
1232
1233 if __name__ == "__main__":
1234     import doctest, bb
1235     doctest.testmod(bb)