Order upgrades according to their dependencies.

        (topological sort using
        Kahn's algorithm - http://en.wikipedia.org/wiki/Topological_sorting).

        :param upgrades: Dict of upgrades
        :param history: Dict of applied upgrades
491545
def order_upgrades(self, upgrades, history=None):
        
        history = history or {}
        graph_incoming, graph_outgoing = self._create_graph(upgrades, history)

        # Removed already applied upgrades (assumes all dependencies prior to
        # this upgrade has been applied).
        for node_id in six.iterkeys(history):
            start_nodes = [node_id, ]
            while start_nodes:
                node = start_nodes.pop()
                # Remove from direct dependents
                try:
                    for d in graph_outgoing[node]:
                        graph_incoming[d] = [x for x in graph_incoming[d]
                                             if x != node]
                except KeyError:
                    warnings.warn("Ghost upgrade %s detected" % node)

                # Remove all prior dependencies
                if node in graph_incoming:
                    # Get dependencies, remove node, and recursively
                    # remove all dependencies.
                    depends_on = graph_incoming[node]

                    # Add dependencies to check
                    for d in depends_on:
                        graph_outgoing[d] = [x for x in graph_outgoing[d]
                                             if x != node]
                        start_nodes.append(d)

                    del graph_incoming[node]

        # Check for missing dependencies
        for node_id, depends_on in six.iteritems(graph_incoming):
            for d in depends_on:
                if d not in graph_incoming:
                    raise RuntimeError("Upgrade %s depends on an unknown"
                                       " upgrade %s" % (node_id, d))

        # Nodes with no incoming edges
        start_nodes = [x for x in six.iterkeys(graph_incoming)
                       if len(graph_incoming[x]) == 0]
        topo_order = []

        while start_nodes:
            # Append node_n to list (it has no incoming edges)
            node_n = start_nodes.pop()
            topo_order.append(node_n)

            # For each node m with and edge from n to m
            for node_m in graph_outgoing[node_n]:
                # Remove the edge n to m
                graph_incoming[node_m] = [x for x in graph_incoming[node_m]
                                          if x != node_n]
                # If m has no incoming edges, add it to start_nodes.
                if not graph_incoming[node_m]:
                    start_nodes.append(node_m)

        for node, edges in six.iteritems(graph_incoming):
            if edges:
                raise RuntimeError("The upgrades have at least one cyclic "
                                   "dependency involving %s." % node)

        return map(lambda x: upgrades[x], topo_order)
1255126
def reorder_release_entries(releases):
    
    order = {'feature': 0, 'bug': 1, 'support': 2}
    for release in releases:
        entries = release['entries'][:]
        release['entries'] = sorted(entries, key=lambda x: order[x.type])
174737
def _load_upgrades(self, remove_applied=True):
        
        if remove_applied:
            self.load_history()

        for entry_point in iter_entry_points('invenio_upgrader.upgrades'):
            upgrade = entry_point.load()()
            self.__class__._upgrades[upgrade.name] = upgrade

        return self.__class__._upgrades
760681
def list_upgrades(bin_env=None,
                  user=None,
                  cwd=None):
    '''
    
    '''
    cmd = _get_pip_bin(bin_env)
    cmd.extend(['list', '--outdated'])

    pip_version = version(bin_env)
    # Pip started supporting the ability to output json starting with 9.0.0
    min_version = '9.0'
    if salt.utils.versions.compare(ver1=pip_version,
                                   oper='>=',
                                   ver2=min_version):
        cmd.append('--format=json')

    cmd_kwargs = dict(cwd=cwd, runas=user)
    if bin_env and os.path.isdir(bin_env):
        cmd_kwargs['env'] = {'VIRTUAL_ENV': bin_env}

    result = __salt__['cmd.run_all'](cmd, **cmd_kwargs)
    if result['retcode']:
        raise CommandExecutionError(result['stderr'], info=result)

    packages = {}
    # Pip started supporting the ability to output json starting with 9.0.0
    # Older versions will have to parse stdout
    if salt.utils.versions.compare(ver1=pip_version, oper='<', ver2='9.0.0'):
        # Pip versions < 8.0.0 had a different output format
        # Sample data:
        # pip (Current: 7.1.2 Latest: 10.0.1 [wheel])
        # psutil (Current: 5.2.2 Latest: 5.4.5 [wheel])
        # pyasn1 (Current: 0.2.3 Latest: 0.4.2 [wheel])
        # pycparser (Current: 2.17 Latest: 2.18 [sdist])
        if salt.utils.versions.compare(ver1=pip_version, oper='<', ver2='8.0.0'):
            logger.debug('pip module: Old output format')
            pat = re.compile(r'(\S*)\s+\(.*Latest:\s+(.*)\)')

        # New output format for version 8.0.0+
        # Sample data:
        # pip (8.0.0) - Latest: 10.0.1 [wheel]
        # psutil (5.2.2) - Latest: 5.4.5 [wheel]
        # pyasn1 (0.2.3) - Latest: 0.4.2 [wheel]
        # pycparser (2.17) - Latest: 2.18 [sdist]
        else:
            logger.debug('pip module: New output format')
            pat = re.compile(r'(\S*)\s+\(.*\)\s+-\s+Latest:\s+(.*)')

        for line in result['stdout'].splitlines():
            match = pat.search(line)
            if match:
                name, version_ = match.groups()
            else:
                logger.error('Can\'t parse line \'%s\'', line)
                continue
            packages[name] = version_

    else:
        logger.debug('pip module: JSON output format')
        try:
            pkgs = salt.utils.json.loads(result['stdout'], strict=False)
        except ValueError:
            raise CommandExecutionError('Invalid JSON', info=result)

        for pkg in pkgs:
            packages[pkg['name']] = '{0} [{1}]'.format(pkg['latest_version'],
                                                       pkg['latest_filetype'])

    return packages
1088224
def upgrade_all(self):
        
        for pkg in self.installed_package_names:
            self.install(pkg, upgrade=True)
207038
def check():
    """"""
    upgrader = InvenioUpgrader()
    logger = upgrader.get_logger()

    try:
        # Run upgrade pre-checks
        upgrades = upgrader.get_upgrades()

        # Check if there's anything to upgrade
        if not upgrades:
            logger.info("All upgrades have been applied.")
            return

        logger.info("Following upgrade(s) have not been applied yet:")
        for u in upgrades:
            logger.info(
                " * {0} {1}".format(u.name, u.info))

        logger.info("Running pre-upgrade checks...")
        upgrader.pre_upgrade_checks(upgrades)
        logger.info("Upgrade check successful - estimated time for upgrading"
                    " Invenio is %s..." % upgrader.human_estimate(upgrades))
    except RuntimeError as e:
        for msg in e.args:
            logger.error(unicode(msg))
        logger.error("Upgrade check failed. Aborting.")
        raise
744658
function upgrade(template) {
  var info = templates.get(template) ||
      set(templates, template, transform(template));
  return {
    template: template,
    updates: fixUpdates.call(this, info.updates),
    chunks: info.chunks
  };
}
482033
def get_upgrade(self, using=None, **kwargs):
        
        return self._get_connection(using).indices.get_upgrade(index=self._name, **kwargs)
650310
def list_upgrades(refresh=True, **kwargs):
    '''
    
    '''

    # sample output of 'xbps-install -un':
    #     fuse-2.9.4_4 update i686 http://repo.voidlinux.eu/current 298133 91688
    #     xtools-0.34_1 update noarch http://repo.voidlinux.eu/current 21424 10752

    refresh = salt.utils.data.is_true(refresh)

    # Refresh repo index before checking for latest version available
    if refresh:
        refresh_db()

    ret = {}

    # retrieve list of updatable packages
    cmd = 'xbps-install -un'
    out = __salt__['cmd.run'](cmd, output_loglevel='trace')
    for line in out.splitlines():
        if not line:
            continue
        pkg = "base-system"
        ver = "NonNumericValueIsError"
        try:
            pkg, ver = line.split()[0].rsplit('-', 1)
        except (ValueError, IndexError):
            log.error(
                'xbps-query: Unexpected formatting in line: "%s"',
                line
            )
            continue

        log.trace('pkg=%s version=%s', pkg, ver)
        ret[pkg] = ver

    return ret
380555
def sbo_upgrade(skip, flag):
    
    Msg().checking()
    upgrade_names = []
    data = SBoGrep(name="").names()
    blacklist = BlackList().packages(pkgs=data, repo="sbo")
    for pkg in sbo_list():
        status(0.02)
        name = split_package(pkg)[0]
        ver = split_package(pkg)[1]
        if (name in data and name not in skip and name not in blacklist):
            sbo_package = ("{0}-{1}".format(name, SBoGrep(name).version()))
            package = ("{0}-{1}".format(name, ver))
            if LooseVersion(sbo_package) > LooseVersion(package):
                upgrade_names.append(name)
    Msg().done()
    if "--checklist" in flag:
        upgrade_names = choose_upg(upgrade_names)
    return upgrade_names
109973
def _topological_sort(self):
        
        sorted_graph = []
        node_map = self._graph.get_nodes()

        nodes = [NodeVisitor(node_map[node]) for node in node_map]

        def get_pointers_for_edge_nodes(visitor_decorated_node):
            edges = []
            edge_ids = visitor_decorated_node.get_node().get_edges()
            for node in nodes:
                if node.get_id() in edge_ids:
                    edges.append(node)

            return edges

        # node is initially weighted with the number of immediate dependencies
        for node in nodes:
            for edge in get_pointers_for_edge_nodes(node):
                edge.increment()

        # Start with a list of nodes who have no dependents
        resolved = [node for node in nodes if node.get_weight() == 0]

        while resolved:
            node = resolved.pop()
            sorted_graph.append(node)

            for edge in get_pointers_for_edge_nodes(node):
                edge.decrement()
                if edge.get_weight() == 0:
                    resolved.append(edge)

        self._circular_dependencies = [
            node.get_node() for node in nodes if node.get_weight() > 0]

        self._sorted_nodes = list(reversed(
            [node.get_node() for node in sorted_graph]))
893818
def sort_versions(self):
        
        if self.sorted:
            return

        for orderer in (self.solver.package_orderers or []):
            entries = orderer.reorder(self.entries, key=lambda x: x.package)
            if entries is not None:
                self.entries = entries
                self.sorted = True

                if self.pr:
                    self.pr("sorted: %s packages: %s", self.package_name, repr(orderer))
                return

        # default ordering is version descending
        self.entries = sorted(self.entries, key=lambda x: x.version, reverse=True)
        self.sorted = True

        if self.pr:
            self.pr("sorted: %s packages: version descending", self.package_name)
496569
private void doUpgrade(List<StorageDirectory> sds,
                 List<StorageInfo> sdsInfo,
                 final NamespaceInfo nsInfo
                 ) throws IOException {
    assert sds.size() == sdsInfo.size();
    UpgradeThread[] upgradeThreads = new UpgradeThread[sds.size()];
    // start to upgrade
    for (int i=0; i<upgradeThreads.length; i++) {
      final StorageDirectory sd = sds.get(i);
      final StorageInfo si = sdsInfo.get(i);
      UpgradeThread thread = new UpgradeThread(sd, si, nsInfo);
      thread.start();
      upgradeThreads[i] = thread;
    }
    // wait for upgrade to be done
    for (UpgradeThread thread : upgradeThreads) {
      try {
        thread.join();
      } catch (InterruptedException e) {
        throw (InterruptedIOException)new InterruptedIOException().initCause(e);
      }
    }
    // check for errors
    for (UpgradeThread thread : upgradeThreads) {
      if (thread.error != null)
        throw new IOException(thread.error);
    }

    // write version file
    this.layoutVersion = FSConstants.LAYOUT_VERSION;
    assert this.namespaceID == nsInfo.getNamespaceID() :
      "Data-node and name-node layout versions must be the same.";
    this.cTime = nsInfo.getCTime();
    for (StorageDirectory sd :sds) {
      sd.write();
      File prevDir = sd.getPreviousDir();
      File tmpDir = sd.getPreviousTmp();
      // rename tmp to previous
      rename(tmpDir, prevDir);
      LOG.info("Upgrade of " + sd.getRoot()+ " is complete.");
    }
  }
1348042
function upgrade() {
  if (!this.active) {
    return this;
  }
  return this.call(
    'system.listComponents',
    this.localComponents,
    (function(err, result) {
      if (!err && typeof result === 'object') {
        this.remoteComponents = result;
        this.remoteComponents['system._upgraded'] = true;
      }
    }).bind(this)
  );
}
1109861
def get_dependencies(self, version=None):
        '''
        
        '''

        version = _process_version(self, version)
        history = self.get_history()

        for v in reversed(history):
            if BumpableVersion(v['version']) == version:
                return v['dependencies']

        raise ValueError('Version {} not found'.format(version))
1051510
def upgrade_many(upgrade=True, create_examples_all=True):
    
    urls = set()

    def inst(url):
        print('upgrading %s' % url)
        assert url not in urls
        urls.add(url)
        try:
            lib = install_lib(url, upgrade)
            print(' -> %s' % lib)
        except Exception as e:
            print(e)

    ############################
    # github.com
    ############################
    inst('https://github.com/sensorium/Mozzi/zipball/master')
    inst('https://github.com/madsci1016/Arduino-EasyTransfer/zipball/master')
    inst('https://github.com/sparkfun/SevSeg/zipball/master')
    inst(
        'https://github.com/madsci1016/Arduino-SoftEasyTransfer/zipball/master')
    inst('https://github.com/madsci1016/Arduino-PS2X/zipball/master')
# inst('http://github.com/wimleers/flexitimer2/zipball/v1.0')# can't install
    inst('https://github.com/kerinin/arduino-splines/zipball/master')
    inst('https://github.com/asynclabs/WiShield/zipball/master')
    inst('https://github.com/asynclabs/dataflash/zipball/master')
    inst('https://github.com/slugmobile/AtTouch/zipball/master')
    inst(
        'https://github.com/carlynorama/Arduino-Library-Button/zipball/master')
    inst(
        'https://github.com/carlynorama/Arduino-Library-FancyLED/zipball/master')
    inst('https://github.com/markfickett/arduinomorse/zipball/master')
    inst('https://github.com/rocketscream/Low-Power/zipball/master')
    inst(
        'https://github.com/arduino-libraries/CapacitiveSensor/zipball/master')

    ############################
    # arduiniana.org
    ############################
    # TODO: how to get latest version??
    inst('http://arduiniana.org/PString/PString2.zip')
    inst('http://arduiniana.org/Flash/Flash3.zip')
    inst('http://arduiniana.org/NewSoftSerial/NewSoftSerial10c.zip')
    inst('http://arduiniana.org/Streaming/Streaming4.zip')
    inst('http://arduiniana.org/PWMServo/PWMServo.zip')
    inst('http://arduiniana.org/TinyGPS/TinyGPS10.zip')

    ############################
    # google
    ############################
    # TODO: how to get latest version??
    # parse http://code.google.com/p/arduino-pinchangeint/downloads/list

    # simplified version in core
    inst('http://rogue-code.googlecode.com/files/Arduino-Library-Tone.zip')

    inst('http://arduino-playground.googlecode.com/files/LedDisplay03.zip')
    inst('http://sserial2mobile.googlecode.com/files/SSerial2Mobile-1.1.0.zip')
    inst('http://webduino.googlecode.com/files/webduino-1.4.1.zip')
    inst('http://arduino-pid-library.googlecode.com/files/PID_v1.0.1.zip')
    inst('http://ideoarduinolibraries.googlecode.com/files/Qtouch1Wire.zip')
    inst('http://arduino-timerone.googlecode.com/files/TimerOne-v8.zip')
    inst('http://arduinounit.googlecode.com/files/arduinounit-1.4.2.zip')
    inst('http://arduinode.googlecode.com/files/arduinode_0.1.zip')
    inst('http://arduino-edb.googlecode.com/files/EDB_r7.zip')
    inst('http://arduino-dblib.googlecode.com/files/DB.zip')
    inst(
        'http://morse-endecoder.googlecode.com/files/Morse_EnDecoder_2010.12.06.tar.gz')
    inst('http://arduino-pinchangeint.googlecode.com/files/PinChangeInt.zip')
    inst('http://arduino-tvout.googlecode.com/files/TVout_R5.91.zip')
    inst('http://narcoleptic.googlecode.com/files/Narcoleptic_v1a.zip')

    ############################
    # teensy
    ############################
    inst('http://www.pjrc.com/teensy/arduino_libraries/OneWire.zip')
    inst('http://www.pjrc.com/teensy/arduino_libraries/VirtualWire.zip')
    inst('http://www.pjrc.com/teensy/arduino_libraries/FrequencyTimer2.zip')
    inst('http://www.pjrc.com/teensy/arduino_libraries/FreqCount.zip')
    inst('http://www.pjrc.com/teensy/arduino_libraries/FreqMeasure.zip')

    ############################
    # others
    ############################

# too big
#    inst('http://www.state-machine.com/arduino/qp_arduino.zip')

# The owner of this website (download.milesburton.com) has banned your access based on your browser's signature
#     inst('http://download.milesburton.com/Arduino/MaximTemperature/DallasTemperature_370Beta.zip')

    inst('http://www.shikadi.net/files/arduino/SerialIP-1.0.zip')
    inst(
        'http://siggiorn.com/wp-content/uploads/libraries/ArduinoByteBuffer.zip')
    inst(
        'http://siggiorn.com/wp-content/uploads/libraries/ArduinoSerialManager.zip')
    inst('http://arduino-tweet.appspot.com/Library-Twitter-1.2.2.zip')

# can't install
# inst('http://gkaindl.com/php/download.php?key=ArduinoEthernet')

    inst(
        'http://sebastian.setz.name/wp-content/uploads/2011/01/multiCameraIrControl_1-5.zip')
    inst('http://alexandre.quessy.net/static/avr/Tween_01.zip')
    inst(
        'http://www.lpelettronica.it/images/stories/LPM11162_images/Arduino/LPM11162_ArduinoLib_v1.zip')
    # inst('http://nootropicdesign.com/hackvision/downloads/Controllers.zip')
    inst(
        'http://interface.khm.de/wp-content/uploads/2009/01/FreqCounter_1_12.zip')
    inst(
        'http://interface.khm.de/wp-content/uploads/2010/06/FreqPeriod_1_12.zip')

    ############################
    # arduino.cc
    ############################
    inst('http://arduino.cc/playground/uploads/Main/PS2Keyboard002.zip')
    inst('http://arduino.cc/playground/uploads/Code/Metro.zip')
    inst('http://www.arduino.cc/playground/uploads/Main/MsTimer2.zip')

# can't install
# inst('http://www.arduino.cc/playground/uploads/Code/Time.zip')

    inst('http://arduino.cc/playground/uploads/Main/LedControl.zip')

# can't install
# inst('http://www.arduino.cc/playground/uploads/Code/ks0108GLCD.zip')#

    inst('http://arduino.cc/playground/uploads/Code/Bounce.zip')
    inst('http://arduino.cc/playground/uploads/Main/CapacitiveSense003.zip')
    inst('http://arduino.cc/playground/uploads/Main/PinChangeInt.zip')

# can't install
# inst('http://arduino.cc/playground/uploads/Code/TimerThree.zip')

    inst('http://arduino.cc/playground/uploads/Code/TimedAction-1_6.zip')

# can't install
# inst('http://www.arduino.cc/playground/uploads/Code/Time.zip')

    inst('http://arduino.cc/playground/uploads/Code/EventFuse.zip')
    inst('http://arduino.cc/playground/uploads/Code/Charlieplex.zip')
    inst('http://arduino.cc/playground/uploads/Code/DigitalToggle.zip')
    inst('http://arduino.cc/playground/uploads/Code/Enerlib.zip')

    inst('http://arduino.cc/playground/uploads/Code/AdvButton_11.zip')

    # old version
    # inst('http://arduino.cc/playground/uploads/Code/AdvButton.zip')

# can't install
# inst('http://arduino.cc/playground/uploads/Code/SerialDebugger.zip') #

    inst('http://arduino.cc/playground/uploads/Code/MatrixMath.zip')
    inst('http://arduino.cc/playground/uploads/Code/StackArray.zip')
    inst('http://arduino.cc/playground/uploads/Code/StackList.zip')
    inst('http://arduino.cc/playground/uploads/Code/QueueArray.zip')
    inst('http://arduino.cc/playground/uploads/Code/QueueList.zip')
    inst('http://arduino.cc/playground/uploads/Code/Ping-1_3.zip')
    inst('http://www.arduino.cc/playground/uploads/Code/LED.zip')

#    inst('')

    if create_examples_all:
        print('create "all" menu item')
        exampallcreate.create_examples_all()
    print('install finished')
687213
def topological_sort(dependencies, start_nodes):
    
    retval = []
    def edges(node): return dependencies[node][1]
    def in_degree(node): return dependencies[node][0]
    def remove_incoming(node): dependencies[node][0] = in_degree(node) - 1
    while start_nodes:
        node = start_nodes.pop()
        retval.append(node)
        for child in edges(node):
            remove_incoming(child)
            if not in_degree(child):
                start_nodes.append(child)
    leftover_nodes = [node for node in list(dependencies.keys())
                      if in_degree(node) > 0]
    if leftover_nodes:
        raise CyclicDependency(leftover_nodes)
    else:
        return retval