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