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