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