Introduce Cython to the project and document

Cython requires a plugin to allow coverage of cython files, which
was updated in coveragerc. It also means we need to build the
dependencies and install cython for coverage.

Cython requires access to both source and compiled files when
running coverage. We therefore need to install project in develop
mode.

Updated documentation to explain how to run tests without tox but
with coverage

9 files changed, 174 insertions, 3 deletions

diff --git a/.coveragerc b/.coveragerc
index 457c439a6..5b06d817a 100644
--- a/.coveragerc
+++ b/.coveragerc
@@ -1,5 +1,6 @@
 [run]
 concurrency = multiprocessing
+plugins = Cython.Coverage
 
 omit =
   # Omit some internals
@@ -11,6 +12,8 @@ omit =
   */.eggs/*
   # Omit .tox directory
   */.tox/*
+  # Omit a dynamically generated Cython file
+  */stringsource
 
 [report]
 show_missing = True
diff --git a/.gitignore b/.gitignore
index 340d7ebe4..a61a975ac 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,6 +2,13 @@
 src/buildstream/**/*.pyc
 tests/**/*.pyc
 
+# Generated C files
+src/buildstream/**/*.c
+src/buildstream/**/*.so
+
+# Cython report files when using annotations
+src/buildstream/**/*.html
+
 # Build output directory
 build
 
diff --git a/CONTRIBUTING.rst b/CONTRIBUTING.rst
index 921cee909..b128c7f9b 100644
--- a/CONTRIBUTING.rst
+++ b/CONTRIBUTING.rst
@@ -1598,6 +1598,15 @@ can run ``tox`` with ``-r`` or  ``--recreate`` option.
 
      ./setup.py test --addopts 'tests/frontend/buildtrack.py::test_build_track'
 
+   If you want to run coverage, you will need need to add ``BST_CYTHON_TRACE=1``
+   to your environment if you also want coverage on cython files. You could then
+   get coverage by running::
+
+     BST_CYTHON_TRACE=1 coverage run ./setup.py test
+
+   Note that to be able to run ``./setup.py test``, you will need to have ``Cython``
+   installed.
+
 .. tip::
 
    We also have an environment called 'venv' which takes any arguments
@@ -1737,6 +1746,12 @@ You can install it with `pip install snakeviz`. Here is an example invocation:
 
 It will then start a webserver and launch a browser to the relevant page.
 
+.. note::
+
+    If you want to also profile cython files, you will need to add
+    BST_CYTHON_PROFILE=1 and recompile the cython files.
+    ``pip install`` would take care of that.
+
 Profiling specific parts of BuildStream with BST_PROFILE
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 BuildStream can also turn on cProfile for specific parts of execution
@@ -1753,6 +1768,32 @@ call most of `initialized`, for each element. These profile files
 are in the same cProfile format as those mentioned in the previous
 section, and can be analysed in the same way.
 
+Fixing performance issues
+~~~~~~~~~~~~~~~~~~~~~~~~~
+
+BuildStream uses `Cython <https://cython.org/>`_ in order to speed up specific parts of the
+code base.
+
+.. note::
+
+    When optimizing for performance, please ensure that you optimize the algorithms before
+    jumping into Cython code. Cython will make the code harder to maintain and less accessible
+    to all developers.
+
+When adding a new cython file to the codebase, you will need to register it in ``setup.py``.
+
+For example, for a module ``buildstream._my_module``, to be written in ``src/buildstream/_my_module.pyx``, you would do::
+
+   register_cython_module("buildstream._my_module")
+
+In ``setup.py`` and the build tool will automatically use your module.
+
+.. note::
+
+   Please register cython modules at the same place as the others.
+
+When adding a definition class to share cython symbols between modules, please document the implementation file
+and only expose the required definitions.
 
 Managing data files
 -------------------
diff --git a/MANIFEST.in b/MANIFEST.in
index 7be35c0be..07369c481 100644
--- a/MANIFEST.in
+++ b/MANIFEST.in
@@ -6,6 +6,11 @@ include MAINTAINERS
 include NEWS
 include README.rst
 
+# Cython files
+recursive-include src/buildstream *.pyx
+recursive-include src/buildstream *.pxd
+recursive-include src/buildstream *.c
+
 # Data files required by BuildStream's generic source tests
 recursive-include src/buildstream/testing/_sourcetests/project *
 
diff --git a/pyproject.toml b/pyproject.toml
index 38bb870e3..4dd02d1e5 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -3,6 +3,7 @@ requires = [
     # We need at least version 36.6.0 that introduced "build_meta"
     "setuptools>=36.6.0",
     # In order to build wheels, and as required by PEP 517
-    "wheel"
+    "wheel",
+    "Cython"
 ]
 build-backend = "setuptools.build_meta"
diff --git a/requirements/cov-requirements.in b/requirements/cov-requirements.in
index 455b91ba6..fb582f816 100644
--- a/requirements/cov-requirements.in
+++ b/requirements/cov-requirements.in
@@ -1,2 +1,3 @@
 coverage == 4.4.0
 pytest-cov >= 2.5.0
+Cython
diff --git a/requirements/cov-requirements.txt b/requirements/cov-requirements.txt
index 843df85f3..a8ba7843b 100644
--- a/requirements/cov-requirements.txt
+++ b/requirements/cov-requirements.txt
@@ -1,4 +1,5 @@
 coverage==4.4
+cython==0.29.7
 pytest-cov==2.6.1
 ## The following requirements were added by pip freeze:
 atomicwrites==1.3.0
diff --git a/setup.py b/setup.py
index 0caf7bae9..fe977c123 100755
--- a/setup.py
+++ b/setup.py
@@ -17,6 +17,7 @@
 #
 #  Authors:
 #        Tristan Van Berkom <tristan.vanberkom@codethink.co.uk>
+#        Benjamin Schubert <bschubert15@bloomberg.net>
 
 import os
 from pathlib import Path
@@ -41,7 +42,7 @@ if sys.version_info[0] != REQUIRED_PYTHON_MAJOR or sys.version_info[1] < REQUIRE
     sys.exit(1)
 
 try:
-    from setuptools import setup, find_packages, Command
+    from setuptools import setup, find_packages, Command, Extension
     from setuptools.command.easy_install import ScriptWriter
     from setuptools.command.test import test as TestCommand
 except ImportError:
@@ -305,6 +306,93 @@ with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),
 
 
 #####################################################
+#            Setup Cython and extensions            #
+#####################################################
+# We want to ensure that source distributions always
+# include the .c files, in order to allow users to
+# not need cython when building.
+def assert_cython_required():
+    if "sdist" not in sys.argv:
+        return
+
+    print("Cython is required when building 'sdist' in order to "
+          "ensure source distributions can be built without Cython. "
+          "Please install it using your package manager (usually 'python3-cython') "
+          "or pip (pip install cython).",
+          file=sys.stderr)
+
+    raise SystemExit(1)
+
+
+extension_macros = [
+    ("CYTHON_TRACE", os.environ.get("BST_CYTHON_TRACE", 0))
+]
+
+
+def cythonize(extensions, **kwargs):
+    try:
+        from Cython.Build import cythonize as _cythonize
+    except ImportError:
+        assert_cython_required()
+
+        print("Cython not found. Using preprocessed c files instead")
+
+        missing_c_sources = []
+
+        for extension in extensions:
+            for source in extension.sources:
+                if source.endswith(".pyx"):
+                    c_file = source.replace(".pyx", ".c")
+
+                    if not os.path.exists(c_file):
+                        missing_c_sources.append((extension, c_file))
+
+        if missing_c_sources:
+            for extension, source in missing_c_sources:
+                print("Missing '{}' for building extension '{}'".format(source, extension.name))
+
+            raise SystemExit(1)
+        return extensions
+
+    return _cythonize(extensions, **kwargs)
+
+
+def register_cython_module(module_name, dependencies=None):
+    def files_from_module(modname):
+        basename = "src/{}".format(modname.replace(".", "/"))
+        return "{}.pyx".format(basename), "{}.pxd".format(basename)
+
+    if dependencies is None:
+        dependencies = []
+
+    implementation_file, definition_file = files_from_module(module_name)
+
+    assert os.path.exists(implementation_file)
+
+    depends = []
+    if os.path.exists(definition_file):
+        depends.append(definition_file)
+
+    for module in dependencies:
+        imp_file, def_file = files_from_module(module)
+        assert os.path.exists(imp_file), "Dependency file not found: {}".format(imp_file)
+        assert os.path.exists(def_file), "Dependency declaration file not found: {}".format(def_file)
+
+        depends.append(imp_file)
+        depends.append(def_file)
+
+    BUILD_EXTENSIONS.append(Extension(
+        name=module_name,
+        sources=[implementation_file],
+        depends=depends,
+        define_macros=extension_macros,
+    ))
+
+
+BUILD_EXTENSIONS = []
+
+
+#####################################################
 #             Main setup() Invocation               #
 #####################################################
 setup(name='BuildStream',
@@ -362,4 +450,16 @@ setup(name='BuildStream',
       install_requires=install_requires,
       entry_points=bst_install_entry_points,
       tests_require=dev_requires,
+      ext_modules=cythonize(
+          BUILD_EXTENSIONS,
+          compiler_directives={
+              # Version of python to use
+              # https://cython.readthedocs.io/en/latest/src/userguide/source_files_and_compilation.html#arguments
+              "language_level": "3",
+              # Enable line tracing, this is needed in order to generate coverage.
+              # This is not enabled unless the CYTHON_TRACE macro for distutils is defined.
+              "linetrace": True,
+              "profile": os.environ.get("BST_CYTHON_PROFILE", False),
+          }
+      ),
       zip_safe=False)
diff --git a/tox.ini b/tox.ini
index 0a269c17d..94e96d9b0 100644
--- a/tox.ini
+++ b/tox.ini
@@ -12,6 +12,10 @@ isolated_build = true
 # Anything specified here is inherited by the sections
 #
 [testenv]
+usedevelop =
+    # This is required by Cython in order to get coverage for cython files.
+    py{35,36,37}-!nocover: True
+
 commands =
     # Running with coverage reporting enabled
     py{35,36,37}-!external-!nocover: pytest --basetemp {envtmpdir} --cov=buildstream --cov-config .coveragerc {posargs}
@@ -52,6 +56,8 @@ setenv =
     py{35,36,37}: XDG_CACHE_HOME = {envtmpdir}/cache
     py{35,36,37}: XDG_CONFIG_HOME = {envtmpdir}/config
     py{35,36,37}: XDG_DATA_HOME = {envtmpdir}/share
+    # This is required to get coverage for Cython
+    py{35,36,37}-!nocover: BST_CYTHON_TRACE = 1
 
 whitelist_externals =
     py{35,36,37}:
@@ -62,7 +68,9 @@ whitelist_externals =
 # Coverage reporting
 #
 [testenv:coverage]
-skip_install = true
+# This is required by Cython in order to get coverage for cython files.
+usedevelop = True
+
 commands =
     coverage combine --rcfile={toxinidir}/.coveragerc {toxinidir}/.coverage-reports/
     coverage html --rcfile={toxinidir}/.coveragerc --directory={toxinidir}/.coverage-reports/
@@ -76,6 +84,10 @@ setenv =
 # Running linters
 #
 [testenv:lint]
+commands_pre =
+    # Build C extensions to allow Pylint to analyse them
+    {envpython} setup.py build_ext --inplace
+
 commands =
     pycodestyle
     pylint src/buildstream tests