model: simplify how get_commits_stats task group on author

Avoid using the caching h.person . We want to get rid of the model
dependency on helpers.

The stats are persisted, and any temporary incorrectness in the long term
cached h.person will thus remain forever. It is thus arguably better to avoid
using it in this place.

get_commits_stats is also a long running task, so speed is not *that* critical.
And generally, processing commits in order will have a lot of the same
committers, so a local cache will have a good hit rate.

(Alternatively, h.person could perhaps be in user model ... but that's not how
it is now.)

kallithea/model/async_tasks.py

@@ -1,509 +1,527 b''
 # -*- coding: utf-8 -*-
 # This program is free software: you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
 # the Free Software Foundation, either version 3 of the License, or
 # (at your option) any later version.
 #
 # This program is distributed in the hope that it will be useful,
 # but WITHOUT ANY WARRANTY; without even the implied warranty of
 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 # GNU General Public License for more details.
 #
 # You should have received a copy of the GNU General Public License
 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
 """
 kallithea.model.async_tasks
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Kallithea task modules, containing all task that suppose to be run
 by celery daemon
 
 This file was forked by the Kallithea project in July 2014.
 Original author and date, and relevant copyright and licensing information is below:
 :created_on: Oct 6, 2010
 :author: marcink
 :copyright: (c) 2013 RhodeCode GmbH, and others.
 :license: GPLv3, see LICENSE.md for more details.
 """
 
 import email.message
 import email.utils
 import os
 import smtplib
 import time
 import traceback
 from collections import OrderedDict
 from operator import itemgetter
 from time import mktime
 
 import celery.utils.log
 from tg import config
 
 import kallithea
-import kallithea.lib.helpers as h
 from kallithea.lib import celerylib, conf, ext_json, hooks
 from kallithea.lib.indexers.daemon import WhooshIndexingDaemon
 from kallithea.lib.utils2 import asbool, ascii_bytes
-from kallithea.lib.vcs.utils import author_email
+from kallithea.lib.vcs.utils import author_email, author_name
 from kallithea.model import db, repo, userlog
 
 
 __all__ = ['whoosh_index', 'get_commits_stats', 'send_email']
 
 
 log = celery.utils.log.get_task_logger(__name__)
 
 
 @celerylib.task
 @celerylib.locked_task
 @celerylib.dbsession
 def whoosh_index(repo_location, full_index):
     celerylib.get_session() # initialize database connection
 
     index_location = config['index_dir']
     WhooshIndexingDaemon(index_location=index_location,
                          repo_location=repo_location) \
                          .run(full_index=full_index)
 
 
+def _author_username(author):
+    """Return the username of the user identified by the email part of the 'author' string,
+    default to the name or email.
+    Kind of similar to h.person() ."""
+    email = author_email(author)
+    if email:
+        user = db.User.get_by_email(email)
+        if user is not None:
+            return user.username
+    # Still nothing?  Just pass back the author name if any, else the email
+    return author_name(author) or email
+
+
 @celerylib.task
 @celerylib.dbsession
 def get_commits_stats(repo_name, ts_min_y, ts_max_y, recurse_limit=100):
     DBS = celerylib.get_session()
     lockkey = celerylib.__get_lockkey('get_commits_stats', repo_name, ts_min_y,
                             ts_max_y)
     lockkey_path = config.get('cache_dir') or config['app_conf']['cache_dir']  # Backward compatibility for TurboGears < 2.4
 
     log.info('running task with lockkey %s', lockkey)
 
     try:
         lock = celerylib.DaemonLock(os.path.join(lockkey_path, lockkey))
 
         co_day_auth_aggr = {}
         commits_by_day_aggregate = {}
         db_repo = db.Repository.get_by_repo_name(repo_name)
         if db_repo is None:
             return True
 
         scm_repo = db_repo.scm_instance
         repo_size = scm_repo.count()
         # return if repo have no revisions
         if repo_size < 1:
             lock.release()
             return True
 
         skip_date_limit = True
         parse_limit = int(config.get('commit_parse_limit'))
         last_rev = None
         last_cs = None
         timegetter = itemgetter('time')
 
         dbrepo = DBS.query(db.Repository) \
             .filter(db.Repository.repo_name == repo_name).scalar()
         cur_stats = DBS.query(db.Statistics) \
             .filter(db.Statistics.repository == dbrepo).scalar()
 
         if cur_stats is not None:
             last_rev = cur_stats.stat_on_revision
 
         if last_rev == scm_repo.get_changeset().revision and repo_size > 1:
             # pass silently without any work if we're not on first revision or
             # current state of parsing revision(from db marker) is the
             # last revision
             lock.release()
             return True
 
         if cur_stats:
             commits_by_day_aggregate = OrderedDict(ext_json.loads(
                                         cur_stats.commit_activity_combined))
             co_day_auth_aggr = ext_json.loads(cur_stats.commit_activity)
 
         log.debug('starting parsing %s', parse_limit)
 
         last_rev = last_rev + 1 if last_rev and last_rev >= 0 else 0
         log.debug('Getting revisions from %s to %s',
              last_rev, last_rev + parse_limit
         )
+        usernames_cache = {}
         for cs in scm_repo[last_rev:last_rev + parse_limit]:
             log.debug('parsing %s', cs)
             last_cs = cs  # remember last parsed changeset
             tt = cs.date.timetuple()
             k = mktime(tt[:3] + (0, 0, 0, 0, 0, 0))
 
-            username = h.person(cs.author)
+            # get username from author - similar to what h.person does
+            username = usernames_cache.get(cs.author)
+            if username is None:
+                username = _author_username(cs.author)
+                usernames_cache[cs.author] = username
+
             if username in co_day_auth_aggr:
                 try:
                     l = [timegetter(x) for x in
                          co_day_auth_aggr[username]['data']]
                     time_pos = l.index(k)
                 except ValueError:
                     time_pos = None
 
                 if time_pos is not None and time_pos >= 0:
                     datadict = \
                         co_day_auth_aggr[username]['data'][time_pos]
 
                     datadict["commits"] += 1
                     datadict["added"] += len(cs.added)
                     datadict["changed"] += len(cs.changed)
                     datadict["removed"] += len(cs.removed)
 
                 else:
                     if k >= ts_min_y and k <= ts_max_y or skip_date_limit:
 
                         datadict = {"time": k,
                                     "commits": 1,
                                     "added": len(cs.added),
                                     "changed": len(cs.changed),
                                     "removed": len(cs.removed),
                                    }
                         co_day_auth_aggr[username]['data'] \
                             .append(datadict)
 
             else:
                 if k >= ts_min_y and k <= ts_max_y or skip_date_limit:
                     co_day_auth_aggr[username] = {
                                         "label": username,
                                         "data": [{"time": k,
                                                  "commits": 1,
                                                  "added": len(cs.added),
                                                  "changed": len(cs.changed),
                                                  "removed": len(cs.removed),
                                                  }],
                                         "schema": ["commits"],
                                         }
 
             # gather all data by day
             if k in commits_by_day_aggregate:
                 commits_by_day_aggregate[k] += 1
             else:
                 commits_by_day_aggregate[k] = 1
 
         overview_data = sorted(commits_by_day_aggregate.items(),
                                key=itemgetter(0))
 
         stats = cur_stats if cur_stats else db.Statistics()
         stats.commit_activity = ascii_bytes(ext_json.dumps(co_day_auth_aggr))
         stats.commit_activity_combined = ascii_bytes(ext_json.dumps(overview_data))
 
         log.debug('last revision %s', last_rev)
         leftovers = len(scm_repo.revisions[last_rev:])
         log.debug('revisions to parse %s', leftovers)
 
         if last_rev == 0 or leftovers < parse_limit:
             log.debug('getting code trending stats')
             stats.languages = ascii_bytes(ext_json.dumps(__get_codes_stats(repo_name)))
 
         try:
             stats.repository = dbrepo
             stats.stat_on_revision = last_cs.revision if last_cs else 0
             DBS.add(stats)
             DBS.commit()
         except:
             log.error(traceback.format_exc())
             DBS.rollback()
             lock.release()
             return False
 
         # final release
         lock.release()
 
         # execute another task if celery is enabled
         if len(scm_repo.revisions) > 1 and kallithea.CELERY_APP and recurse_limit > 0:
             get_commits_stats(repo_name, ts_min_y, ts_max_y, recurse_limit - 1)
         elif recurse_limit <= 0:
             log.debug('Not recursing - limit has been reached')
         else:
             log.debug('Not recursing')
     except celerylib.LockHeld:
         log.info('Task with key %s already running', lockkey)
         return 'Task with key %s already running' % lockkey
 
 
 @celerylib.task
 @celerylib.dbsession
 def send_email(recipients, subject, body='', html_body='', headers=None, from_name=None):
     """
     Sends an email with defined parameters from the .ini files.
 
     :param recipients: list of recipients, if this is None, the defined email
         address from field 'email_to' and all admins is used instead
     :param subject: subject of the mail
     :param body: plain text body of the mail
     :param html_body: html version of body
     :param headers: dictionary of prepopulated e-mail headers
     :param from_name: full name to be used as sender of this mail - often a
     .full_name_or_username value
     """
     assert isinstance(recipients, list), recipients
     if headers is None:
         headers = {}
     else:
         # do not modify the original headers object passed by the caller
         headers = headers.copy()
 
     email_config = config
     email_prefix = email_config.get('email_prefix', '')
     if email_prefix:
         subject = "%s %s" % (email_prefix, subject)
 
     if not recipients:
         # if recipients are not defined we send to email_config + all admins
         recipients = [u.email for u in db.User.query()
                       .filter(db.User.admin == True).all()]
         if email_config.get('email_to') is not None:
             recipients += email_config.get('email_to').split(',')
 
         # If there are still no recipients, there are no admins and no address
         # configured in email_to, so return.
         if not recipients:
             log.error("No recipients specified and no fallback available.")
             return False
 
         log.warning("No recipients specified for '%s' - sending to admins %s", subject, ' '.join(recipients))
 
     # SMTP sender
     app_email_from = email_config.get('app_email_from', 'Kallithea')
     # 'From' header
     if from_name is not None:
         # set From header based on from_name but with a generic e-mail address
         # In case app_email_from is in "Some Name <e-mail>" format, we first
         # extract the e-mail address.
         envelope_addr = author_email(app_email_from)
         headers['From'] = '"%s" <%s>' % (
             email.utils.quote('%s (no-reply)' % from_name),
             envelope_addr)
 
     smtp_server = email_config.get('smtp_server')
     smtp_port = email_config.get('smtp_port')
     smtp_use_tls = asbool(email_config.get('smtp_use_tls'))
     smtp_use_ssl = asbool(email_config.get('smtp_use_ssl'))
     smtp_auth = email_config.get('smtp_auth')  # undocumented - overrule automatic choice of auth mechanism
     smtp_username = email_config.get('smtp_username')
     smtp_password = email_config.get('smtp_password')
 
     logmsg = ("Mail details:\n"
               "recipients: %s\n"
               "headers: %s\n"
               "subject: %s\n"
               "body:\n%s\n"
               "html:\n%s\n"
               % (' '.join(recipients), headers, subject, body, html_body))
 
     if smtp_server:
         log.debug("Sending e-mail. " + logmsg)
     else:
         log.error("SMTP mail server not configured - cannot send e-mail.")
         log.warning(logmsg)
         return False
 
     msg = email.message.EmailMessage()
     msg['Subject'] = subject
     msg['From'] = app_email_from  # fallback - might be overridden by a header
     msg['To'] = ', '.join(recipients)
     msg['Date'] = email.utils.formatdate(time.time())
 
     for key, value in headers.items():
         del msg[key]  # Delete key first to make sure add_header will replace header (if any), no matter the casing
         msg.add_header(key, value)
 
     msg.set_content(body)
     msg.add_alternative(html_body, subtype='html')
 
     try:
         if smtp_use_ssl:
             smtp_serv = smtplib.SMTP_SSL(smtp_server, smtp_port)
         else:
             smtp_serv = smtplib.SMTP(smtp_server, smtp_port)
 
         if smtp_use_tls:
             smtp_serv.starttls()
 
         if smtp_auth:
             smtp_serv.ehlo()  # populate esmtp_features
             smtp_serv.esmtp_features["auth"] = smtp_auth
 
         if smtp_username and smtp_password is not None:
             smtp_serv.login(smtp_username, smtp_password)
 
         smtp_serv.sendmail(app_email_from, recipients, msg.as_string())
         smtp_serv.quit()
 
         log.info('Mail was sent to: %s' % recipients)
     except:
         log.error('Mail sending failed')
         log.error(traceback.format_exc())
         return False
     return True
 
 
 @celerylib.task
 @celerylib.dbsession
 def create_repo(form_data, cur_user):
     DBS = celerylib.get_session()
 
     cur_user = db.User.guess_instance(cur_user)
 
     owner = cur_user
     repo_name = form_data['repo_name']
     repo_name_full = form_data['repo_name_full']
     repo_type = form_data['repo_type']
     description = form_data['repo_description']
     private = form_data['repo_private']
     clone_uri = form_data.get('clone_uri')
     repo_group = form_data['repo_group']
     landing_rev = form_data['repo_landing_rev']
     copy_fork_permissions = form_data.get('copy_permissions')
     copy_group_permissions = form_data.get('repo_copy_permissions')
     fork_of = form_data.get('fork_parent_id')
     state = form_data.get('repo_state', db.Repository.STATE_PENDING)
 
     # repo creation defaults, private and repo_type are filled in form
     defs = db.Setting.get_default_repo_settings(strip_prefix=True)
     enable_statistics = defs.get('repo_enable_statistics')
     enable_downloads = defs.get('repo_enable_downloads')
 
     try:
         db_repo = repo.RepoModel()._create_repo(
             repo_name=repo_name_full,
             repo_type=repo_type,
             description=description,
             owner=owner,
             private=private,
             clone_uri=clone_uri,
             repo_group=repo_group,
             landing_rev=landing_rev,
             fork_of=fork_of,
             copy_fork_permissions=copy_fork_permissions,
             copy_group_permissions=copy_group_permissions,
             enable_statistics=enable_statistics,
             enable_downloads=enable_downloads,
             state=state
         )
 
         userlog.action_logger(cur_user, 'user_created_repo',
                       form_data['repo_name_full'], '')
 
         DBS.commit()
         # now create this repo on Filesystem
         repo.RepoModel()._create_filesystem_repo(
             repo_name=repo_name,
             repo_type=repo_type,
             repo_group=db.RepoGroup.guess_instance(repo_group),
             clone_uri=clone_uri,
         )
         db_repo = db.Repository.get_by_repo_name(repo_name_full)
         hooks.log_create_repository(db_repo.get_dict(), created_by=owner.username)
 
         # update repo changeset caches initially
         db_repo.update_changeset_cache()
 
         # set new created state
         db_repo.set_state(db.Repository.STATE_CREATED)
         DBS.commit()
     except Exception as e:
         log.warning('Exception %s occurred when forking repository, '
                     'doing cleanup...' % e)
         # rollback things manually !
         db_repo = db.Repository.get_by_repo_name(repo_name_full)
         if db_repo:
             db.Repository.delete(db_repo.repo_id)
             DBS.commit()
             repo.RepoModel()._delete_filesystem_repo(db_repo)
         raise
 
     return True
 
 
 @celerylib.task
 @celerylib.dbsession
 def create_repo_fork(form_data, cur_user):
     """
     Creates a fork of repository using interval VCS methods
 
     :param form_data:
     :param cur_user:
     """
     DBS = celerylib.get_session()
 
     base_path = kallithea.CONFIG['base_path']
     cur_user = db.User.guess_instance(cur_user)
 
     repo_name = form_data['repo_name']  # fork in this case
     repo_name_full = form_data['repo_name_full']
 
     repo_type = form_data['repo_type']
     owner = cur_user
     private = form_data['private']
     clone_uri = form_data.get('clone_uri')
     repo_group = form_data['repo_group']
     landing_rev = form_data['landing_rev']
     copy_fork_permissions = form_data.get('copy_permissions')
 
     try:
         fork_of = db.Repository.guess_instance(form_data.get('fork_parent_id'))
 
         repo.RepoModel()._create_repo(
             repo_name=repo_name_full,
             repo_type=repo_type,
             description=form_data['description'],
             owner=owner,
             private=private,
             clone_uri=clone_uri,
             repo_group=repo_group,
             landing_rev=landing_rev,
             fork_of=fork_of,
             copy_fork_permissions=copy_fork_permissions
         )
         userlog.action_logger(cur_user, 'user_forked_repo:%s' % repo_name_full,
                       fork_of.repo_name, '')
         DBS.commit()
 
         source_repo_path = os.path.join(base_path, fork_of.repo_name)
 
         # now create this repo on Filesystem
         repo.RepoModel()._create_filesystem_repo(
             repo_name=repo_name,
             repo_type=repo_type,
             repo_group=db.RepoGroup.guess_instance(repo_group),
             clone_uri=source_repo_path,
         )
         db_repo = db.Repository.get_by_repo_name(repo_name_full)
         hooks.log_create_repository(db_repo.get_dict(), created_by=owner.username)
 
         # update repo changeset caches initially
         db_repo.update_changeset_cache()
 
         # set new created state
         db_repo.set_state(db.Repository.STATE_CREATED)
         DBS.commit()
     except Exception as e:
         log.warning('Exception %s occurred when forking repository, '
                     'doing cleanup...' % e)
         # rollback things manually !
         db_repo = db.Repository.get_by_repo_name(repo_name_full)
         if db_repo:
             db.Repository.delete(db_repo.repo_id)
             DBS.commit()
             repo.RepoModel()._delete_filesystem_repo(db_repo)
         raise
 
     return True
 
 
 def __get_codes_stats(repo_name):
     scm_repo = db.Repository.get_by_repo_name(repo_name).scm_instance
 
     tip = scm_repo.get_changeset()
     code_stats = {}
 
     for _topnode, _dirnodes, filenodes in tip.walk('/'):
         for filenode in filenodes:
             ext = filenode.extension.lower()
             if ext in conf.LANGUAGES_EXTENSIONS_MAP and not filenode.is_binary:
                 if ext in code_stats:
                     code_stats[ext] += 1
                 else:
                     code_stats[ext] = 1
 
     return code_stats or {}

scripts/deps.py

@@ -1,294 +1,293 b''
 #!/usr/bin/env python3
 
 
 import re
 import sys
 
 
 ignored_modules = set('''
 argparse
 base64
 bcrypt
 binascii
 bleach
 calendar
 celery
 celery
 chardet
 click
 collections
 configparser
 copy
 csv
 ctypes
 datetime
 dateutil
 decimal
 decorator
 difflib
 distutils
 docutils
 email
 errno
 fileinput
 functools
 getpass
 grp
 hashlib
 hmac
 html
 http
 imp
 importlib
 inspect
 io
 ipaddr
 IPython
 isapi_wsgi
 itertools
 json
 kajiki
 ldap
 logging
 mako
 markdown
 mimetypes
 mock
 msvcrt
 multiprocessing
 operator
 os
 paginate
 paginate_sqlalchemy
 pam
 paste
 pkg_resources
 platform
 posixpath
 pprint
 pwd
 pyflakes
 pytest
 pytest_localserver
 random
 re
 routes
 setuptools
 shlex
 shutil
 smtplib
 socket
 ssl
 stat
 string
 struct
 subprocess
 sys
 tarfile
 tempfile
 textwrap
 tgext
 threading
 time
 traceback
 traitlets
 types
 urllib
 urlobject
 uuid
 warnings
 webhelpers2
 webob
 webtest
 whoosh
 win32traceutil
 zipfile
 '''.split())
 
 top_modules = set('''
 kallithea.alembic
 kallithea.bin
 kallithea.config
 kallithea.controllers
 kallithea.templates.py
 scripts
 '''.split())
 
 bottom_external_modules = set('''
 tg
 mercurial
 sqlalchemy
 alembic
 formencode
 pygments
 dulwich
 beaker
 psycopg2
 docs
 setup
 conftest
 '''.split())
 
 normal_modules = set('''
 kallithea
 kallithea.controllers.base
 kallithea.lib
 kallithea.lib.auth
 kallithea.lib.auth_modules
 kallithea.lib.celerylib
 kallithea.lib.db_manage
 kallithea.lib.helpers
 kallithea.lib.hooks
 kallithea.lib.indexers
 kallithea.lib.utils
 kallithea.lib.utils2
 kallithea.lib.vcs
 kallithea.lib.webutils
 kallithea.model
 kallithea.model.async_tasks
 kallithea.model.scm
 kallithea.templates.py
 '''.split())
 
 shown_modules = normal_modules | top_modules
 
 # break the chains somehow - this is a cleanup TODO list
 known_violations = [
 ('kallithea.lib.auth_modules', 'kallithea.lib.auth'),  # needs base&facade
 ('kallithea.lib.utils', 'kallithea.model'),  # clean up utils
 ('kallithea.lib.utils', 'kallithea.model.db'),
 ('kallithea.lib.utils', 'kallithea.model.scm'),
-('kallithea.model.async_tasks', 'kallithea.lib.helpers'),
 ('kallithea.model.async_tasks', 'kallithea.lib.hooks'),
 ('kallithea.model.async_tasks', 'kallithea.lib.indexers'),
 ('kallithea.model.async_tasks', 'kallithea.model'),
 ('kallithea.model', 'kallithea.lib.auth'),  # auth.HasXXX
 ('kallithea.model', 'kallithea.lib.auth_modules'),  # validators
 ('kallithea.model', 'kallithea.lib.hooks'),  # clean up hooks
 ('kallithea.model', 'kallithea.model.scm'),
 ('kallithea.model.scm', 'kallithea.lib.hooks'),
 ]
 
 extra_edges = [
 ('kallithea.config', 'kallithea.controllers'),  # through TG
 ('kallithea.lib.auth', 'kallithea.lib.auth_modules'),  # custom loader
 ]
 
 
 def normalize(s):
     """Given a string with dot path, return the string it should be shown as."""
     parts = s.replace('.__init__', '').split('.')
     short_2 = '.'.join(parts[:2])
     short_3 = '.'.join(parts[:3])
     short_4 = '.'.join(parts[:4])
     if parts[0] in ['scripts', 'contributor_data', 'i18n_utils']:
         return 'scripts'
     if short_3 == 'kallithea.model.meta':
         return 'kallithea.model.db'
     if parts[:4] == ['kallithea', 'lib', 'vcs', 'ssh']:
         return 'kallithea.lib.vcs.ssh'
     if short_4 in shown_modules:
         return short_4
     if short_3 in shown_modules:
         return short_3
     if short_2 in shown_modules:
         return short_2
     if short_2 == 'kallithea.tests':
         return None
     if parts[0] in ignored_modules:
         return None
     assert parts[0] in bottom_external_modules, parts
     return parts[0]
 
 
 def main(filenames):
     if not filenames or filenames[0].startswith('-'):
         print('''\
 Usage:
     hg files 'set:!binary()&grep("^#!.*python")' 'set:**.py' | xargs scripts/deps.py
     dot -Tsvg deps.dot > deps.svg
         ''')
         raise SystemExit(1)
 
     files_imports = dict()  # map filenames to its imports
     import_deps = set()  # set of tuples with module name and its imports
     for fn in filenames:
         with open(fn) as f:
             s = f.read()
 
         dot_name = (fn[:-3] if fn.endswith('.py') else fn).replace('/', '.')
         file_imports = set()
         for m in re.finditer(r'^ *(?:from ([^ ]*) import (?:([a-zA-Z].*)|\(([^)]*)\))|import (.*))$', s, re.MULTILINE):
             m_from, m_from_import, m_from_import2, m_import = m.groups()
             if m_from:
                 pre = m_from + '.'
                 if pre.startswith('.'):
                     pre = dot_name.rsplit('.', 1)[0] + pre
                 importlist = m_from_import or m_from_import2
             else:
                 pre = ''
                 importlist = m_import
             for imp in importlist.split('#', 1)[0].split(','):
                 full_imp = pre + imp.strip().split(' as ', 1)[0]
                 file_imports.add(full_imp)
                 import_deps.add((dot_name, full_imp))
         files_imports[fn] = file_imports
 
     # dump out all deps for debugging and analysis
     with open('deps.txt', 'w') as f:
         for fn, file_imports in sorted(files_imports.items()):
             for file_import in sorted(file_imports):
                 if file_import.split('.', 1)[0] in ignored_modules:
                     continue
                 f.write('%s: %s\n' % (fn, file_import))
 
     # find leafs that haven't been ignored - they are the important external dependencies and shown in the bottom row
     only_imported = set(
         set(normalize(b) for a, b in import_deps) -
         set(normalize(a) for a, b in import_deps) -
         set([None, 'kallithea'])
     )
 
     normalized_dep_edges = set()
     for dot_name, full_imp in import_deps:
         a = normalize(dot_name)
         b = normalize(full_imp)
         if a is None or b is None or a == b:
             continue
         normalized_dep_edges.add((a, b))
         #print((dot_name, full_imp, a, b))
     normalized_dep_edges.update(extra_edges)
 
     unseen_shown_modules = shown_modules.difference(a for a, b in normalized_dep_edges).difference(b for a, b in normalized_dep_edges)
     assert not unseen_shown_modules, unseen_shown_modules
 
     with open('deps.dot', 'w') as f:
         f.write('digraph {\n')
         f.write('subgraph { rank = same; %s}\n' % ''.join('"%s"; ' % s for s in sorted(top_modules)))
         f.write('subgraph { rank = same; %s}\n' % ''.join('"%s"; ' % s for s in sorted(only_imported)))
         for a, b in sorted(normalized_dep_edges):
             f.write('  "%s" -> "%s"%s\n' % (a, b, ' [color=red]' if (a, b) in known_violations else ' [color=green]' if (a, b) in extra_edges else ''))
         f.write('}\n')
 
     # verify dependencies by untangling dependency chain bottom-up:
     todo = set(normalized_dep_edges)
     for x in known_violations:
         todo.remove(x)
 
     while todo:
         depending = set(a for a, b in todo)
         depended = set(b for a, b in todo)
         drop = depended - depending
         if not drop:
             print('ERROR: cycles:', len(todo))
             for x in sorted(todo):
                 print('%s,' % (x,))
             raise SystemExit(1)
         #for do_b in sorted(drop):
         #    print('Picking', do_b, '- unblocks:', ' '.join(a for a, b in sorted((todo)) if b == do_b))
         todo = set((a, b) for a, b in todo if b in depending)
         #print()
 
 
 if __name__ == '__main__':
     main(sys.argv[1:])