feat(third_party/bazel): Check in rules_haskell from Tweag r/17

4 files changed, 629 insertions, 0 deletions

diff --git a/third_party/bazel/rules_haskell/debug/linking_utils/BUILD.bazel b/third_party/bazel/rules_haskell/debug/linking_utils/BUILD.bazel
new file mode 100644
index 000000000000..a32be2cfb6f9
--- /dev/null
+++ b/third_party/bazel/rules_haskell/debug/linking_utils/BUILD.bazel
@@ -0,0 +1,50 @@
+load(
+    ":ldd_test.bzl",
+    "ldd_test",
+)
+
+py_library(
+    name = "linking_utils",
+    srcs = ["ldd.py"],
+    visibility = ["//visibility:public"],
+)
+
+# test the ldd debug library on the output of `//tests/binary-indirect-cbits`
+ldd_test(
+    name = "test-ldd",
+    current_workspace = None,
+    elf_binary = "//tests/binary-indirect-cbits",
+    script = r'''
+import sys
+
+def contains_error(error):
+    """check whether any of the dependencies contains `error`,
+    where error is something from `LDD_ERRORS`.
+    Returns {} if there's no error.
+    """
+    def f(d):
+        return { k: v for k, v in d['needed'].items()
+          if (v == error
+             or (v not in LDD_ERRORS
+                and dict_remove_empty(v['item']) != {})) }
+    return f
+
+# output should have some runpaths
+assert \
+    ldd(identity, sys.argv[1])['runpath_dirs']\
+    > 0
+
+# some of the dependencies are implicit and not in NEEDED flags
+assert ldd(contains_error(LDD_UNKNOWN), sys.argv[1])
+
+import pprint
+# none of the dependencies must be missing
+res = ldd(contains_error(LDD_MISSING), sys.argv[1])
+if res != {}:
+  print("These dependencies are missing:")
+  pprint.pprint(res)
+  exit(1)
+''',
+    # it only works on linux
+    tags = ["dont_test_on_darwin"],
+)
diff --git a/third_party/bazel/rules_haskell/debug/linking_utils/README.md b/third_party/bazel/rules_haskell/debug/linking_utils/README.md
new file mode 100644
index 000000000000..57384a27fe54
--- /dev/null
+++ b/third_party/bazel/rules_haskell/debug/linking_utils/README.md
@@ -0,0 +1,265 @@
+# Debugging linking errors
+
+The usual utilities, like `nm`, `objdump`, and of course `ldd` (see
+[here](https://linux-audit.com/elf-binaries-on-linux-understanding-and-analysis/#tools-for-binary-analysis)
+for a good overview of existing tools) go a long way. Yet, when
+debugging non-trivial runtime linker failures one would oftentimes
+like to filter outputs programmatically, with more advanced query
+logic than just simple `grep` and `sed` expressions.
+
+This library provides a small set of utility subroutines. These can
+help debug complicated linker errors.
+
+The main function is `ldd(f, elf_path)`. It is in the same spirit
+as `ldd(1)`, but instead of a flat list of resolved libraries, it
+returns a tree of structured information.
+
+When we use the term `ldd` in the following document, it refers
+to the `ldd` function exported from [./ldd.py](./ldd.py).
+
+To query that tree, you pass it a function `f`, which is applied to
+each dependency recursively (transforming the tree from the bottom
+up).
+
+The following functions are exported alongside the `ldd` function.
+They can be passed to `ldd` and used as building blocks for insightful
+queries:
+
+- `identity`: don’t transform, output everything
+- `remove_matching_needed`: remove needed entries that match a regex
+- `remove_matching_runpaths`: remove runpaths that match a regex
+- `non_existing_runpaths`: return a list of runpaths that don’t exist
+  in the filesystem
+- `unused_runpaths`: return a list of runpaths that are listed in the
+  elf binary header, but no dependency was actually found in them
+- `collect_unused_runpaths`: give an overview of all unused runpaths
+
+Helpers:
+- `dict_remove_empty`: remove fields with empty lists/dicts from an output
+- `items`: `dict.iteritems()` for both python 2 and 3
+
+See the introductory tutorial below on how to use these functions.
+
+## Example usage
+
+### Setup
+
+If you have a bazel target which outputs a binary which you want to
+debug, the easiest way is to use `ldd_test`:
+
+```python
+load(
+    "//:debug/linking_utils/ldd_test.bzl",
+    "ldd_test",
+)
+
+ldd_test(
+    name = "test-ldd",
+    elf_binary = "//tests/binary-indirect-cbits",
+    current_workspace = None,
+    script = r'''
+YOUR SCRIPT HERE
+'''
+)
+```
+
+All exported functions from `ldd.py` are already in scope.
+See the [`BUILD`](./BUILD) file in this directory for an example.
+
+
+### Writing queries
+
+`ldd` takes a function that is applied to each layer of elf
+dependencies. This function is passed a set of structured data.
+This data is gathered by querying the elf binary with `objdump`
+and parsing the header fields of the dynamic section:
+
+```
+DependencyInfo :
+{ needed : dict(string, union(
+    LDD_MISSING, LDD_UNKNOWN,
+    {
+        # the needed dependency
+        item : a,
+        # where the dependency was found in
+        found_in : RunpathDir
+    }))
+# all runpath directories that were searched
+, runpath_dirs : [ RunpathDir ] }
+```
+
+The amount of data can get quite extensive for larger projects, so you
+need a way to filter it down to get to the bottom of our problem.
+
+If a transitive dependency cannot be found by the runtime linker, the
+binary cannot be started. `ldd` shows such a problem by setting
+the corresponding value in the `needed` dict to `LDD_MISSING`.
+To remove everything from the output but the missing dependency and
+the path to that dependency, you can write a filter like this:
+
+```python
+# `d` is the DependencyInfo dict from above
+def filter_down_to_missing(d):
+    res = {}
+
+    # items is a .iteritems() that works for py 2 and 3
+    for name, dep in items(d['needed']):
+        if dep == LDD_MISSING:
+            res[name] = LDD_MISSING
+        elif dep in LDD_ERRORS:
+            pass
+        else:
+            # dep['item'] contains the already converted info
+            # from the previous layer
+            res[name] = dep['item']
+
+    # dict_remove_empty removes all empty fields from the dict,
+    # otherwise your result contains a lot of {} in the values.
+    return dict_remove_empty(res)
+
+# To get human-readable output, we re-use python’s pretty printing
+# library. It’s only simple python values after all!
+import pprint
+pprint.pprint(
+  # actually parse the elf binary and apply only_missing on each layer
+  ldd(
+    filter_down_to_missing,
+    # the path to the elf binary you want to expect.
+    elf_binary_path
+  )
+)
+```
+
+Note that in the filter you only need to filter the data for the
+current executable, and add the info from previous layers (which are
+available in `d['item']`).
+
+The result might look something like:
+
+```python
+{'libfoo.so.5': {'libbar.so.1': {'libbaz.so.6': 'MISSING'}}}
+```
+
+or
+
+```python
+{}
+```
+
+if nothing is missing.
+
+Now, that is a similar output to what a tool like `lddtree(1)` could
+give you. But we don’t need to stop there because it’s trivial to
+augment your output with more information:
+
+
+```python
+def missing_with_runpath(d):
+  # our previous function can be re-used
+  missing = filter_down_to_missing(d)
+
+  # only display runpaths if there are missing deps
+  runpaths = [] if missing is {} else d['runpath_dirs']
+
+  # dict_remove_empty keeps the output clean
+  return dict_remove_empty({
+    'rpth': runpaths,
+    'miss': missing
+  })
+
+# same invocation, different function
+pprint.pprint(
+  ldd(
+    missing_with_runpath,
+    elf_binary_path
+  )
+)
+```
+
+which displays something like this for my example binary:
+
+```python
+{ 'miss': { 'libfoo.so.5': { 'miss': { 'libbar.so.1': { 'miss': { 'libbaz.so.6': 'MISSING'},
+                                                          'rpth': [ { 'absolute_path': '/home/philip/.cache/bazel/_bazel_philip/fd9fea5ad581ea59473dc1f9d6bce826/execroot/myproject/bazel-out/k8-fastbuild/bin/something/and/bazel-out/k8-fastbuild/bin/other/integrate',
+                                                                      'path': '$ORIGIN/../../../../../../bazel-out/k8-fastbuild/bin/other/integrate'}]}},
+                             'rpth': [ { 'absolute_path': '/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib',
+                                         'path': '/nix/store/xdsjx0gba4id3yyqxv66bxnm2sqixkjj-glibc-2.27/lib'},
+                                       { 'absolute_path': '/nix/store/x6inizi5ahlyhqxxwv1rvn05a25icarq-gcc-7.3.0-lib/lib',
+                                         'path': '/nix/store/x6inizi5ahlyhqxxwv1rvn05a25icarq-gcc-7.3.0-lib/lib'}]}},
+  'rpth': [ … lots more nix rpaths … ]}
+```
+
+That’s still a bit cluttered for my taste, so let’s filter out
+the `/nix/store` paths (which are mostly noise):
+
+```python
+import re
+nix_matcher = re.compile("/nix/store.*")
+
+def missing_with_runpath(d):
+  missing = filter_down_to_missing(d)
+
+  # this is one of the example functions provided by ldd.py
+  remove_matching_runpaths(d, nix_matcher)
+  # ^^^
+
+  runpaths = [] if missing is {} else d['runpath_dirs']
+
+  # dict_remove_empty keeps the output clean
+  return dict_remove_empty({
+    'rpth': runpaths,
+    'miss': missing
+  })
+```
+
+and we are down to:
+
+```python
+{ 'miss': { 'libfoo.so.5': { 'miss': { 'libbar.so.1': { 'miss': { 'libbaz.so.6': 'MISSING'},
+                                                          'rpth': [ { 'absolute_path': '/home/philip/.cache/bazel/_bazel_philip/fd9fea5ad581ea59473dc1f9d6bce826/execroot/myproject/bazel-out/k8-fastbuild/bin/something/and/bazel-out/k8-fastbuild/bin/other/integrate',
+                                                                      'path': '$ORIGIN/../../../../../../bazel-out/k8-fastbuild/bin/other/integrate'}]}}}
+```
+
+… which shows exactly the path that is missing the dependency we
+expect. But what has gone wrong? Does this path even exist? We can
+find out!
+
+```python
+import re
+nix_matcher = re.compile("/nix/store.*")
+
+def missing_with_runpath(d):
+  missing = filter_down_to_missing(d)
+  remove_matching_runpaths(d, nix_matcher)
+  runpaths = [] if missing is {} else d['runpath_dirs']
+
+  # returns a list of runpaths that don’t exist in the filesystem
+  doesnt_exist = non_existing_runpaths(d)
+  # ^^^
+
+  return dict_remove_empty({
+    'rpth': runpaths,
+    'miss': missing,
+    'doesnt_exist': doesnt_exist,
+  })
+```
+
+I amended the output by a list of runpaths which point to non-existing
+directories:
+
+```python
+{ 'miss': { 'libfoo.so.5': { 'miss': { 'libbar.so.1': { 'miss': { 'libbaz.so.6': 'MISSING'},
+                                                        'rpth': [ { 'absolute_path': '/home/philip/.cache/bazel/_bazel_philip/fd9fea5ad581ea59473dc1f9d6bce826/execroot/myproject/bazel-out/k8-fastbuild/bin/something/and/bazel-out/k8-fastbuild/bin/other/integrate',
+                                                                    'path': '$ORIGIN/../../../../../../bazel-out/k8-fastbuild/bin/other/integrate'}]
+                                                        'doesnt_exist': [ { 'absolute_path': '/home/philip/.cache/bazel/_bazel_philip/fd9fea5ad581ea59473dc1f9d6bce826/execroot/myproject/bazel-out/k8-fastbuild/bin/something/and/bazel-out/k8-fastbuild/bin/other/integrate',
+                                                                            'path': '$ORIGIN/../../../../../../bazel-out/k8-fastbuild/bin/other/integrate'}]}}}
+```
+
+Suddenly it’s perfectly clear where the problem lies,
+`$ORIGIN/../../../../../../bazel-out/k8-fastbuild/bin/other/integrate`
+points to a path that does not exist.
+
+Any data query you’d like to do is possible, as long as it uses
+the data provided by the `ldd` function. See the lower part of
+`ldd.py` for more examples.
+
diff --git a/third_party/bazel/rules_haskell/debug/linking_utils/ldd.py b/third_party/bazel/rules_haskell/debug/linking_utils/ldd.py
new file mode 100644
index 000000000000..897cfdc713d3
--- /dev/null
+++ b/third_party/bazel/rules_haskell/debug/linking_utils/ldd.py
@@ -0,0 +1,288 @@
+import subprocess
+import os
+import sys
+import re
+
+
+### helper functions
+
+def list_to_dict(f, l):
+    """dict with elements of list as keys & as values transformed by f"""
+    d = {}
+    for el in l:
+        d[el] = f(el)
+    return d
+
+def dict_remove_empty(d):
+    """remove keys that have [] or {} or as values"""
+    new = {}
+    for k, v in d.items():
+        if not (v == [] or v == {}):
+             new[k] = v
+    return new
+
+def identity(x):
+    """identity function"""
+    return x
+
+def const(x):
+    """(curried) constant function"""
+    def f(y):
+        return x
+    return f
+
+def memoized(cache, f, arg):
+    """Memoizes a call to `f` with `arg` in the dict `cache`.
+    Modifies the cache dict in place."""
+    res = cache.get(arg)
+    if arg in cache:
+        return cache[arg]
+    else:
+        res = f(arg)
+        cache[arg] = res
+        return res
+
+### IO functions that find elf dependencies
+
+_field_matcher = re.compile(b"  ([A-Z0-9_]+) +(.*)$")
+
+def read_dynamic_fields(elf_path):
+    """Read the dynamic header fields from an elf binary
+
+    Args:
+      elf_path: path to the elf binary (either absolute or relative to pwd)
+
+    Returns:
+      a list [(field_key, field_value)] where field_keys could appear multiple
+      times (for example there's usually more than one NEEDED field).
+    """
+    res = subprocess.check_output([
+        # force locale to C for stable output
+        "env", "LC_ALL=C",
+        "objdump",
+        # specifying the section brings execution time down from 150ms to 10ms
+        "--section=.dynamic",
+        "--all-headers",
+        elf_path
+    ])
+    to_end = res.split(b"Dynamic Section:\n")[1]
+    # to first empty line
+    dyn_section = to_end[: 1 + to_end.find(b"\n\n")]
+    def read_dynamic_field(s):
+        """return (field_key, field_value)"""
+        return _field_matcher.match(s).groups()
+    return list(map(read_dynamic_field, dyn_section.splitlines(True)))
+
+def __query_dynamic_fields(df, key):
+    """takes a list of dynamic field tuples (key and value),
+    where keys can appear multiple times, and returns a list of all
+    values with the given key (in stable order)."""
+    return [v for k, v in df if k == key]
+
+def parse_runpath_dirs(elf_path, elf_dynamic_fields):
+    """Parse a RUNPATH entry from an elf header bytestring.
+
+    Returns:
+      { path: unmodified string from DT_RUNPATH
+      , absolute_path: fully normalized, absolute path to dir }
+    """
+    fields = __query_dynamic_fields(elf_dynamic_fields, b"RUNPATH")
+    if fields == []:
+        return []
+    assert len(fields) == 1
+    val = fields[0]
+    origin = os.path.dirname(elf_path)
+    return [{ 'path': path,
+              'absolute_path': os.path.abspath(path.replace("$ORIGIN", origin)) }
+            for path in val.decode().strip(":").split(":")
+            if path != ""]
+
+def parse_needed(elf_dynamic_fields):
+    """Returns the list of DT_NEEDED entries for elf"""
+    return [n.decode() for n in __query_dynamic_fields(elf_dynamic_fields, b"NEEDED")]
+
+
+### Main utility
+
+# cannot find dependency
+LDD_MISSING = "MISSING"
+# don't know how to search for dependency
+LDD_UNKNOWN = "DUNNO"
+# list of all errors for easy branching
+LDD_ERRORS = [ LDD_MISSING, LDD_UNKNOWN ]
+
+def _ldd(elf_cache, f, elf_path):
+    """Same as `ldd` (below), except for an additional `elf_cache` argument,
+    which is a dict needed for memoizing elf files that were already read.
+    This is done because the elf reading operation is quite expensive
+    and many files are referenced multiple times (e.g. glib.so)."""
+
+    def search(rdirs, elf_libname):
+        """search for elf_libname in runfile dirs
+        and return either the name or missing"""
+        res = LDD_MISSING
+        for rdir in rdirs:
+            potential_path = os.path.join(rdir['absolute_path'], elf_libname)
+            if os.path.exists(potential_path):
+                res = {
+                    'item': potential_path,
+                    'found_in': rdir,
+                }
+                break
+        return res
+
+    def recurse(search_res):
+        """Unfold the subtree of ELF dependencies for a `search` result"""
+        if search_res == LDD_MISSING:
+            return LDD_MISSING
+        else:
+            # we keep all other fields in search_res the same,
+            # just item is the one that does the recursion.
+            # This is the part that would normally be done by fmap.
+            search_res['item'] = _ldd(elf_cache, f, search_res['item'])
+            return search_res
+
+    # (GNU) ld.so resolves any symlinks before searching for dependencies
+    elf_realpath = os.path.realpath(elf_path)
+
+    # memoized uses the cache to not repeat the I/O action
+    # for the same elf files (same path)
+    dyn_fields = memoized(
+        elf_cache, read_dynamic_fields, elf_realpath
+    )
+    rdirs = parse_runpath_dirs(elf_realpath, dyn_fields)
+    all_needed = parse_needed(dyn_fields)
+
+    # if there's no runpath dirs we don't know where to search
+    if rdirs == []:
+        needed = list_to_dict(const(LDD_UNKNOWN), all_needed)
+    else:
+        needed = list_to_dict(
+            lambda name: recurse(search(rdirs, name)),
+            all_needed
+        )
+
+    result = {
+        'runpath_dirs': rdirs,
+        'needed': needed
+    }
+    # Here, f is applied to the result of the previous level of recursion
+    return f(result)
+
+
+def ldd(f, elf_path):
+    """follows DT_NEEDED ELF headers for elf by searching the through DT_RUNPATH.
+
+    DependencyInfo :
+    { needed : dict(string, union(
+        LDD_MISSING, LDD_UNKNOWN,
+        {
+            # the needed dependency
+            item : a,
+            # where the dependency was found in
+            found_in : RunpathDir
+        }))
+    # all runpath directories that were searched
+    , runpath_dirs : [ RunpathDir ] }
+
+    Args:
+        f: DependencyInfo -> a
+        modifies the results of each level
+        elf_path: path to ELF file, either absolute or relative to current working dir
+
+    Returns: a
+    """
+    elf_cache = {}
+    return _ldd(elf_cache, f, elf_path)
+
+
+### Functions to pass to ldd
+
+# Only use the current layer
+
+def remove_matching_needed(d, re_matcher_absolute_path=None, re_matcher_path=None):
+    """Destructively removes needed values from d['needed']
+    if they match the given regex matcher.
+    Doesn't remove LDD_ERRORS."""
+    def pred(v):
+        """return true if match"""
+        if v in LDD_ERRORS:
+            return False
+        found_in = v['found_in']
+        abs_match = re_matcher_absolute_path.match(found_in['absolute_path']) \
+                    if re_matcher_absolute_path else False
+        match = re_matcher_path.match(found_in['path']) \
+                    if re_matcher_path else False
+        if abs_match or match:
+            return True
+    d['needed'] = {
+        k: v for k, v in d['needed'].items()
+        if not pred(v)
+    }
+
+def remove_matching_runpaths(d, re_matcher):
+    """Destructively removes runpaths from d['runpath_dirs']
+    if they match the given regex matcher."""
+    d['runpath_dirs'] = [
+        runp for runp in d['runpath_dirs']
+        if not re_matcher.match(runp['absolute_path'])
+    ]
+    return d
+
+def non_existing_runpaths(d):
+    """Return a list of runpaths_dirs that do not exist in the file system."""
+    return [
+        runp for runp in d['runpath_dirs']
+        if not os.path.exists(runp['absolute_path'])
+    ]
+
+def unused_runpaths(d):
+    """Return a list of runpath_dirs that were not used to find NEEDED dependencies."""
+    used = set()
+    for k, v in d['needed'].items():
+        if not v in LDD_ERRORS:
+            used.add(v['found_in']['absolute_path'])
+    return [
+        u for u in d['runpath_dirs']
+        if u['absolute_path'] not in used
+    ]
+
+# Also use the results of sub-layers
+
+def collect_unused_runpaths(d):
+    """This is like `unused_runpaths`, but it creates a deduplicated list of all unused runpaths
+    for its dependencies instead of just returning them for the current layer.
+
+    Returns:
+      a dict of two fields;
+      `mine` contains the unused dependencies of the current binary under scrutiny
+      `others` contains a flat dict of all .sos with unused runpath entries and a list of them for each .so
+    """
+    used = set()
+    given = set(r['absolute_path'] for r in d['runpath_dirs'])
+    prev = {}
+    # TODO: use `unused_runpaths` here
+    for k, v in d['needed'].items():
+        if not v in LDD_ERRORS:
+            used.add(v['found_in']['absolute_path'])
+            prev[k] = v['item']
+    unused = [
+        u for u in given.difference(used)
+        # leave out nix storepaths
+        if not u.startswith("/nix/store")
+    ]
+
+    # Each layer doesn't know about their own name
+    # So we return a list of unused for this layer ('mine')
+    # and a dict of all previeous layers combined (name to list)
+    def combine_unused(deps):
+        res = {}
+        for name, dep in deps.items():
+            res.update(dep['others'])
+            res[name] = dep['mine']
+        return res
+
+    return {
+        'mine': unused,
+        'others': combine_unused(prev),
+    }
diff --git a/third_party/bazel/rules_haskell/debug/linking_utils/ldd_test.bzl b/third_party/bazel/rules_haskell/debug/linking_utils/ldd_test.bzl
new file mode 100644
index 000000000000..5872828df282
--- /dev/null
+++ b/third_party/bazel/rules_haskell/debug/linking_utils/ldd_test.bzl
@@ -0,0 +1,26 @@
+load(
+    "//:tests/inline_tests.bzl",
+    "py_inline_test",
+)
+
+#
+def ldd_test(name, elf_binary, script, current_workspace = None, tags = []):
+    """Test with imported linking_utils.ldd library.
+    The path to the `elf_binary` is passed in sys.argv[1].
+    """
+    py_inline_test(
+        name,
+        deps = ["@io_tweag_rules_haskell//debug/linking_utils"],
+        data = [elf_binary],
+        args = ["{}/$(rootpath {})".format(current_workspace, elf_binary)] if current_workspace else ["$(rootpath {})".format(elf_binary)],
+        script = """
+from io_tweag_rules_haskell.debug.linking_utils.ldd import \\
+        dict_remove_empty, identity, const, \\
+        LDD_MISSING, LDD_UNKNOWN, LDD_ERRORS, \\
+        ldd, \\
+        remove_matching_needed, remove_matching_runpaths, \\
+        non_existing_runpaths, unused_runpaths, \\
+        collect_unused_runpaths
+""" + script,
+        tags = tags,
+    )