lib/bb/__init__.py

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