Implement context solver on node level

6 files changed, 199 insertions, 75 deletions

diff --git a/sugar_network/model/__init__.py b/sugar_network/model/__init__.py
index 7278d10..6858957 100644
--- a/sugar_network/model/__init__.py
+++ b/sugar_network/model/__init__.py
@@ -141,6 +141,7 @@ def load_bundle(blob, context=None, initial=False, extra_deps=None):
     release_notes = None
     release = {}
     blob_meta = {}
+    version = None
 
     try:
         bundle = Bundle(blob.path, mime_type='application/zip')
@@ -148,7 +149,7 @@ def load_bundle(blob, context=None, initial=False, extra_deps=None):
         context_type = 'book'
         if not context:
             context = this.request['context']
-        release['version'] = this.request['version']
+        version = this.request['version']
         if 'license' in this.request:
             release['license'] = this.request['license']
             if isinstance(release['license'], basestring):
@@ -180,29 +181,21 @@ def load_bundle(blob, context=None, initial=False, extra_deps=None):
         if extra_deps:
             spec.requires.update(parse_requires(extra_deps))
 
-        release['version'] = spec['version']
+        version = spec['version']
         release['stability'] = spec['stability']
         if spec['license'] is not EMPTY_LICENSE:
             release['license'] = spec['license']
-        release['requires'] = requires = []
-        for dep_name, dep in spec.requires.items():
-            found = False
-            for version in dep.versions_range():
-                requires.append('%s-%s' % (dep_name, version))
-                found = True
-            if not found:
-                requires.append(dep_name)
+        release['commands'] = spec.commands
+        release['requires'] = spec.requires
         release['spec'] = {'*-*': {
             'bundle': blob.digest,
-            'commands': spec.commands,
-            'requires': spec.requires,
             }}
         release['unpack_size'] = unpack_size
         blob_meta['mime_type'] = 'application/vnd.olpc-sugar'
 
     enforce(context, http.BadRequest, 'Context is not specified')
-    enforce(release['version'], http.BadRequest, 'Version is not specified')
-    release['release'] = parse_version(release['version'])
+    enforce(version, http.BadRequest, 'Version is not specified')
+    release['version'] = parse_version(version)
     if initial and not contexts.exists(context):
         enforce(context_meta, http.BadRequest, 'No way to initate context')
         context_meta['guid'] = context
@@ -211,21 +204,22 @@ def load_bundle(blob, context=None, initial=False, extra_deps=None):
     else:
         enforce(context_type in contexts[context]['type'],
                 http.BadRequest, 'Inappropriate bundle type')
-    context_obj = contexts[context]
+    context_doc = contexts[context]
 
-    releases = context_obj['releases']
     if 'license' not in release:
+        releases = context_doc['releases'].values()
         enforce(releases, http.BadRequest, 'License is not specified')
-        recent = max(releases, key=lambda x: releases[x]['release'])
-        release['license'] = releases[recent]['license']
+        recent = max(releases, key=lambda x: x.get('value', {}).get('release'))
+        enforce(recent, http.BadRequest, 'License is not specified')
+        release['license'] = recent['value']['license']
 
     _logger.debug('Load %r release: %r', context, release)
 
-    if this.request.principal in context_obj['author']:
-        diff = context_obj.patch(context_meta)
+    if this.request.principal in context_doc['author']:
+        diff = context_doc.patch(context_meta)
         if diff:
             this.call(method='PUT', path=['context', context], content=diff)
-            context_obj.props.update(diff)
+            context_doc.props.update(diff)
         # TRANS: Release notes title
         title = i18n._('%(name)s %(version)s release')
     else:
@@ -236,15 +230,15 @@ def load_bundle(blob, context=None, initial=False, extra_deps=None):
                 'context': context,
                 'type': 'notification',
                 'title': i18n.encode(title,
-                    name=context_obj['title'],
-                    version=release['version'],
+                    name=context_doc['title'],
+                    version=version,
                     ),
                 'message': release_notes or '',
                 },
             content_type='application/json')
 
-    filename = ''.join(i18n.decode(context_obj['title']).split())
-    blob_meta['name'] = '%s-%s' % (filename, release['version'])
+    filename = ''.join(i18n.decode(context_doc['title']).split())
+    blob_meta['name'] = '%s-%s' % (filename, version)
     files.update(blob.digest, blob_meta)
 
     return context, release
diff --git a/sugar_network/model/context.py b/sugar_network/model/context.py
index 6bac120..951aad1 100644
--- a/sugar_network/model/context.py
+++ b/sugar_network/model/context.py
@@ -89,7 +89,7 @@ class Context(db.Resource):
     def rating(self, value):
         return value
 
-    @db.stored_property(db.List, default=[], acl=ACL.PUBLIC | ACL.LOCAL)
+    @db.stored_property(default='', acl=ACL.PUBLIC | ACL.LOCAL)
     def dependencies(self, value):
         """Software dependencies.
 
diff --git a/sugar_network/node/model.py b/sugar_network/node/model.py
index 2681b2d..7276b75 100644
--- a/sugar_network/node/model.py
+++ b/sugar_network/node/model.py
@@ -13,14 +13,15 @@
 # You should have received a copy of the GNU General Public License
 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
+import bisect
 import logging
 
 from sugar_network import db, toolkit
-from sugar_network.model import Release, context
+from sugar_network.model import Release, context as base_context
 from sugar_network.node import obs
 from sugar_network.toolkit.router import ACL
 from sugar_network.toolkit.coroutine import this
-from sugar_network.toolkit import http, coroutine, enforce
+from sugar_network.toolkit import spec, sat, http, coroutine, enforce
 
 
 _logger = logging.getLogger('node.model')
@@ -48,7 +49,7 @@ class _Release(Release):
             lsb_id = distro
             lsb_release = None
         releases = this.resource.record.get('releases')
-        statuses = releases['value'].setdefault('status', {})
+        resolves = releases['value'].setdefault('resolves', {})
         to_presolve = []
 
         for repo in obs.get_repos():
@@ -60,21 +61,26 @@ class _Release(Release):
                     not lsb_release and repo['name'] in releases['value']:
                 continue
             pkgs = sum([value.get(i, []) for i in ('binary', 'devel')], [])
+            version = None
             try:
                 for arch in repo['arches']:
-                    obs.resolve(repo['name'], arch, pkgs)
+                    version = obs.resolve(repo['name'], arch, pkgs)['version']
             except Exception, error:
                 _logger.warning('Failed to resolve %r on %s',
                         pkgs, repo['name'])
-                status = str(error)
+                resolve = {'status': str(error)}
             else:
                 to_presolve.append((repo['name'], pkgs))
-                status = 'success'
-            statuses[repo['name']] = status
+                resolve = {
+                        'version': spec.parse_version(version),
+                        'packages': pkgs,
+                        'status': 'success',
+                        }
+            resolves.setdefault(repo['name'], {}).update(resolve)
 
         if to_presolve and _presolve_queue is not None:
             _presolve_queue.put(to_presolve)
-        if statuses:
+        if resolves:
             this.resource.record.set('releases', **releases)
 
         return value
@@ -85,7 +91,7 @@ class _Release(Release):
         # TODO Delete presolved files
 
 
-class Context(context.Context):
+class Context(base_context.Context):
 
     @db.stored_property(db.Aggregated, subtype=_Release(),
             acl=ACL.READ | ACL.INSERT | ACL.REMOVE | ACL.REPLACE)
@@ -143,15 +149,10 @@ def merge(volume, records):
     for record in records:
         resource_ = record.get('resource')
         if resource_:
-            resource = resource_
             directory = volume[resource_]
             continue
 
         if 'guid' in record:
-            guid = record['guid']
-            existed = directory.exists(guid)
-            if existed:
-                layer = directory.get(guid)['layer']
             seqno, merged = directory.merge(**record)
             synced = synced or merged
             if seqno is not None:
@@ -169,9 +170,144 @@ def merge(volume, records):
     return commit_seq, merged_seq
 
 
+def solve(volume, top_context, lsb_id=None, lsb_release=None,
+        stability=None, requires=None):
+    top_context = volume['context'][top_context]
+    top_stability = stability or ['stable']
+    if isinstance(top_stability, basestring):
+        top_stability = [top_stability]
+    top_cond = None
+    top_requires = {}
+    if isinstance(requires, basestring):
+        top_requires.update(spec.parse_requires(requires))
+    elif requires:
+        for i in requires:
+            top_requires.update(spec.parse_requires(i))
+    if top_context['dependencies']:
+        top_requires.update(spec.parse_requires(top_context['dependencies']))
+    if top_context.guid in top_requires:
+        top_cond = top_requires.pop(top_context.guid)
+
+    lsb_distro = '-'.join([lsb_id, lsb_release]) if lsb_release else None
+    varset = [None]
+    context_clauses = {}
+    clauses = []
+
+    _logger.debug('Solve %r lsb_id=%r lsb_release=%r stability=%r requires=%r',
+            top_context.guid, lsb_id, lsb_release, top_stability, top_requires)
+
+    def ensure_version(version, cond):
+        if not cond:
+            return True
+        for not_before, before in cond['restrictions']:
+            if before is not None and version >= before or \
+                    not_before is not None and version < not_before:
+                return False
+        return True
+
+    def rate_release(digest, release):
+        return [_STABILITY_RATES.get(release['stability']) or 0,
+                release['version'],
+                digest,
+                ]
+
+    def add_deps(context, v_usage, deps):
+        if top_requires and context.guid == top_context.guid:
+            deps.update(top_requires)
+        for dep, cond in deps.items():
+            dep_clause = [-v_usage]
+            for v_release in add_context(dep):
+                if ensure_version(varset[v_release][0], cond):
+                    dep_clause.append(v_release)
+            clauses.append(dep_clause)
+
+    def add_context(context):
+        if context in context_clauses:
+            return context_clauses[context]
+        context = volume['context'][context]
+        releases = context['releases']
+        clause = []
+
+        if 'package' in context['type']:
+            pkg_lst = None
+            pkg_ver = []
+            pkg = releases.get('resolves', {}).get(lsb_distro)
+            if pkg:
+                pkg_ver = pkg['version']
+                pkg_lst = pkg['packages']
+            else:
+                alias = releases.get(lsb_id) or releases.get('*')
+                if alias:
+                    alias = alias['value']
+                    pkg_lst = alias.get('binary', []) + alias.get('devel', [])
+            if pkg_lst:
+                clause.append(len(varset))
+                varset.append((pkg_ver, 'packages', {context.guid: pkg_lst}))
+        else:
+            candidates = []
+            for digest, release in releases.items():
+                if 'value' not in release:
+                    continue
+                release = release['value']
+                if release['stability'] not in top_stability or \
+                        context.guid == top_context.guid and \
+                            not ensure_version(release['version'], top_cond):
+                    continue
+                bisect.insort(candidates, rate_release(digest, release))
+            for release in reversed(candidates):
+                digest = release[-1]
+                release = releases[digest]['value']
+                v_release = len(varset)
+                varset.append((
+                    release['version'],
+                    'files',
+                    {context.guid: digest},
+                    ))
+                clause.append(v_release)
+                add_deps(context, v_release, release.get('requires') or {})
+
+        if clause:
+            context_clauses[context.guid] = clause
+        else:
+            _logger.trace('No candidates for %r', context.guid)
+        return clause
+
+    top_clause = add_context(top_context.guid)
+    if not top_clause:
+        _logger.debug('No versions for %r', top_context.guid)
+        return None
+    result = sat.solve(clauses + [top_clause], context_clauses)
+    if not result:
+        _logger.debug('Failed to solve %r', top_context.guid)
+        return None
+    if not top_context.guid in result:
+        _logger.debug('No top versions for %r', top_context.guid)
+        return None
+
+    solution = {'files': {}, 'packages': {}}
+    for v in result.values():
+        __, key, items = varset[v]
+        solution[key].update(items)
+    top_release = top_context['releases'][solution['files'][top_context.guid]]
+    solution['commands'] = top_release['value']['commands']
+
+    _logger.debug('Solution for %r: %r', top_context.guid, solution)
+
+    return solution
+
+
 def presolve(presolve_path):
     global _presolve_queue
     _presolve_queue = coroutine.Queue()
 
     for repo_name, pkgs in _presolve_queue:
         obs.presolve(repo_name, pkgs, presolve_path)
+
+
+_STABILITY_RATES = {
+        'insecure': 0,
+        'buggy': 1,
+        'developer': 2,
+        'testing': 3,
+        'stable': 4,
+        }
diff --git a/sugar_network/node/obs.py b/sugar_network/node/obs.py
index 6ef9e55..796ea7c 100644
--- a/sugar_network/node/obs.py
+++ b/sugar_network/node/obs.py
@@ -46,12 +46,13 @@ def get_repos():
 
 
 def resolve(repo, arch, packages):
-    _request('GET', ['resolve'], params={
+    response = _request('GET', ['resolve'], params={
         'project': obs_project.value,
         'repository': repo,
         'arch': arch,
         'package': packages,
         })
+    return dict(response.find('binary').items())
 
 
 def presolve(repo_name, packages, dst_path):
diff --git a/sugar_network/node/routes.py b/sugar_network/node/routes.py
index 6323cbc..da6c675 100644
--- a/sugar_network/node/routes.py
+++ b/sugar_network/node/routes.py
@@ -20,9 +20,10 @@ import hashlib
 from ConfigParser import ConfigParser
 from os.path import join, isdir, exists
 
-from sugar_network import db, node, toolkit, model
+from sugar_network import db, node, toolkit
 from sugar_network.db import files
-from sugar_network.node import stats_user
+from sugar_network.model import FrontRoutes, load_bundle
+from sugar_network.node import stats_user, model
 # pylint: disable-msg=W0611
 from sugar_network.toolkit.router import route, preroute, postroute, ACL
 from sugar_network.toolkit.router import Unauthorized, Request, fallbackroute
@@ -39,11 +40,11 @@ _AUTH_POOL_SIZE = 1024
 _logger = logging.getLogger('node.routes')
 
 
-class NodeRoutes(db.Routes, model.FrontRoutes):
+class NodeRoutes(db.Routes, FrontRoutes):
 
     def __init__(self, guid, **kwargs):
         db.Routes.__init__(self, **kwargs)
-        model.FrontRoutes.__init__(self)
+        FrontRoutes.__init__(self)
         self._guid = guid
         self._auth_pool = pylru.lrucache(_AUTH_POOL_SIZE)
         self._auth_config = None
@@ -120,7 +121,7 @@ class NodeRoutes(db.Routes, model.FrontRoutes):
     def submit_release(self, request, initial):
         blob = files.post(request.content_stream)
         try:
-            context, release = model.load_bundle(blob, initial=initial)
+            context, release = load_bundle(blob, initial=initial)
         except Exception:
             files.delete(blob.digest)
             raise
@@ -144,40 +145,24 @@ class NodeRoutes(db.Routes, model.FrontRoutes):
         layer = list(set(doc['layer']) - set(request.content))
         directory.update(request.guid, {'layer': layer})
 
+    @route('GET', ['context', None], cmd='solve',
+            arguments={'requires': list, 'stability': list},
+            mime_type='application/json')
+    def solve(self, request):
+        solution = model.solve(self.volume, request.guid, **request)
+        enforce(solution is not None, 'Failed to solve')
+        return solution
+
     @route('GET', ['context', None], cmd='clone',
             arguments={'requires': list})
     def get_clone(self, request, response):
-        deps = {}
-        if 'requires' in request:
-            for i in request['requires']:
-                deps.update(parse_requires(i))
-        version = request.get('version')
-        if version:
-            version = parse_version(version)[0]
-        stability = request.get('stability') or 'stable'
-
-        recent = None
-        context = self.volume['context'][request.guid]
-        for release in context['releases'].values():
-            release = release.get('value')
-            if not release:
-                continue
-            spec = release['spec']['*-*']
-            if version and version != release['release'][0] or \
-                    stability and stability != release['stability'] or \
-                    deps and not ensure_requires(spec['requires'], deps):
-                continue
-            if recent is None or release['release'] > recent['release']:
-                recent = release
-        enforce(recent, http.NotFound, 'No releases found')
-
-        response.meta = recent
-        return files.get(recent['spec']['*-*']['bundle'])
+        response.meta = self.solve(request)
+        return files.get(response.meta['files'][request.guid])
 
     @route('HEAD', ['context', None], cmd='clone',
             arguments={'requires': list})
     def head_clone(self, request, response):
-        self.get_clone(request, response)
+        response.meta = self.solve(request)
 
     @route('GET', ['user', None], cmd='stats-info',
             mime_type='application/json', acl=ACL.AUTH)
diff --git a/sugar_network/toolkit/sat.py b/sugar_network/toolkit/sat.py
index a908dd7..65afdaf 100644
--- a/sugar_network/toolkit/sat.py
+++ b/sugar_network/toolkit/sat.py
@@ -35,7 +35,7 @@ from sugar_network.toolkit import enforce
 _logger = logging.getLogger('sat')
 
 
-def solve(clauses, at_most_one_clauses, decide):
+def solve(clauses, at_most_one_clauses):
     if not clauses:
         _logger.info('No clauses')
         return None
@@ -55,7 +55,15 @@ def solve(clauses, at_most_one_clauses, decide):
     for name, clause in at_most_one_clauses.items():
         clauses[name] = problem.at_most_one(clause)
 
-    if not problem.run_solver(lambda: decide(clauses)):
+    def decide():
+        for clause in clauses.values():
+            if clause.current is not None:
+                continue
+            v = clause.best_undecided()
+            if v is not None:
+                return v
+
+    if not problem.run_solver(decide):
         return None
 
     result = {}