code.vuplus.com Git - vuplus_bitbake/blob - 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)