Module paroxython.map_taxonomy

Translate labels into taxa.

Description

This step comes after paroxython.label_programs has tagged a program with the labels specified in spec.md. Its purpose is to convert these labels into taxa based on the rules defined (by default) in taxonomy.tsv.

Example

Let's return to the Jupyter notebook's cell given in the introduction:

1   %%paroxython labels
2   def fibonacci(n):
3       result = []
4       (a, b) = (0, 1)
5       while a < n:
6           result.append(a)
7           (a, b) = (b, a + b)
8       return result

Note that the magic cell-command %%paroxython is now called with a labels argument. This produces the following output (limited for brevity to its first four rows):

These labels are low-level tags, intended for internal use only. They still need to be translated into the following taxa, which are the only tags of interest to the end user. For instance, "addition_operator" will be translated into "operator/arithmetic/addition" (note that, unlike a label, a taxon may feature one or several slashes, which indicate the nesting of notions). More examples are given in the dedicated section of the user manual.

In fact, both labels and taxa are couples:

• Label: ("addition_operator", [(7, 7, "...")]).
• Taxon: ("operator/arithmetic/addition", {(7, 7, "..."): 1}).

The second member is slightly more complicated than a list of line numbers:

• For a label, it is a list of triples consisting of the start and end of the spanning lines, and a third member, the path (here denoted by the ellipsis), which identifies unambiguously the start of the span.
• For a taxon, it is a bag, i.e. a dictionary associating such triples with the count of their occurrences in the program.

The paths being left untouched by the conversion, we will omit them from now on.

Deduplication

• Labels:
  • ("assignment", [(3, 3), (4, 4), (7, 7)]).
  • ("single_assignment:result", [(3, 3)]).
  • ("parallel_assignment", [(4, 4), (7, 7)]).
  • ("slide", [(7, 7)]).
• Taxa:
  • ("var/assignment/explicit/single", {(3, 3): 1}).
  • ("var/assignment/explicit/parallel", {(4, 4): 1}).
  • ("var/assignment/explicit/parallel/slide", {(7, 7): 1}).

The example program features three distinct assignments. They can be categorized into:

• A single assignment on line 3 (result = []).
• A parallel assignment on line 4 ((a, b) = (0, 1)).
• A parallel assignment where a couple is updated by “sliding” the value of its second member to the first position, on line 7 ((a, b) = (b, a + b)).

As you can see, labelling all these produces a lot of span redundancies. For instance, the assignment of line 7 is labelled three times, as "assignment", "parallel_assignment" and "slide". Since the labels are not structured, this is the best that we can do.

Enter the taxa, whose production is triggered by the following taxonomy rows:

Initially, the conversion produces as many redundant spans as for the labels:

• Taxa:
  • ("var/assignment/explicit", {(3, 3): 1, (4, 4): 1, (7, 7): 1}).
  • ("var/assignment/explicit/single", {(3, 3): 1}).
  • ("var/assignment/explicit/parallel", {(4, 4): 1, (7, 7): 1}).
  • ("var/assignment/explicit/parallel/slide", {(7, 7): 1}).

However, because of the tree-like structuring of taxa, it is possible to remove those occurrences that are subject to further characterization (e.g., var/assignment/explicit/parallel on line 7 is further characterized as var/assignment/explicit/parallel/slide), resulting in the list of taxa given at the start of the section.

Note that the removal of spans has finally led to the elimination of the overly generic taxon var/assignment/explicit.

from collections import Counter, defaultdict
from pathlib import Path
from typing import Callable, Dict, List, Optional, Tuple
from typing import Pattern as RegexPattern
from os.path import commonpath, dirname
from functools import lru_cache

import regex  # type: ignore

from .user_types import (
    LabelName,
    LabelPattern,
    Labels,
    Taxon,
    TaxonName,
    TaxonNames,
    TaxonPattern,
    Taxa,
    TaxaSpans,
)

__pdoc__ = {
    "Taxonomy.__init__": True,
    "Taxonomy": "",
}


class Taxonomy:
    def __init__(
        self,
        taxonomy_path: Optional[Path] = None,
        **kwargs,
    ) -> None:
        taxonomy_path = taxonomy_path or Path(dirname(__file__)) / "resources" / "taxonomy.tsv"
        tsv = taxonomy_path.read_text().partition("-- EOF")[0].strip()
        self.literal_labels: Dict[LabelName, TaxonNames] = defaultdict(list)
        self.compiled_labels: List[Tuple[RegexPattern, TaxonPattern]] = []
        for line in sorted(tsv.split("\n")[1:]):
            (taxon_value, label_value, *_) = line.strip().split(maxsplit=2)
            (taxon_pattern, label_pattern) = (TaxonPattern(taxon_value), LabelPattern(label_value))
            if is_literal(label_pattern):
                self.literal_labels[LabelName(label_pattern)].append(TaxonName(taxon_pattern))
            else:
                self.compiled_labels.append((regex.compile(f"{label_pattern}$"), taxon_pattern))
                # note: "$" is necessary: regex.fullmatch() has no regex.fullsub() counterpart

    @lru_cache(maxsize=None)
    def get_taxon_name_list(
        self, label_name: LabelName, looks_like_a_taxon: Callable = regex.compile(r"^\w+/.+$").match
    ) -> TaxonNames:
        if looks_like_a_taxon(label_name):
            return [TaxonName(label_name)]
        result: TaxonNames = self.literal_labels.get(label_name, [])
        for (label_regex_pattern, taxon_pattern) in self.compiled_labels:
            if label_regex_pattern.match(label_name):
                result.append(TaxonName(label_regex_pattern.sub(taxon_pattern, label_name)))
        return result

    def to_taxa(self, labels: Labels) -> Taxa:
        acc: TaxaSpans = defaultdict(Counter)
        for (label_name, spans) in labels:
            for taxon_name in self.get_taxon_name_list(label_name):
                acc[taxon_name].update(spans)
        taxa = [Taxon(name, spans) for (name, spans) in sorted(acc.items())]
        return deduplicated_taxa(taxa)


def is_literal(label_pattern: LabelPattern) -> bool:
    return label_pattern.replace(".", "\\.") == regex.escape(label_pattern)


def deduplicated_taxa(taxa: Taxa) -> Taxa:
    if len(taxa) < 2:
        return taxa
    for (i, (name, spans)) in enumerate(taxa[1:], 1):
        for (previous_name, previous_spans) in reversed(taxa[:i]):
            # Since `"/"` happens to be a separator in both taxa and Unix-paths, `os.commonpath()`
            # comes in handy for extracting the common prefix of two taxa:
            common_prefix = commonpath((name, previous_name))
            if not common_prefix:
                break
            if previous_name == common_prefix:
                difference = spans - previous_spans
                previous_spans.subtract(spans)
                spans = difference
    result = []
    for (name, spans) in taxa:
        spans += Counter()  # suppress items whose count <= 0
        if spans:  # if any item remains in the bag
            result.append(Taxon(name, spans))
    return result


if __name__ == "__main__":
    from .goodies import couple_to_string
    from .label_programs import labelled_programs

    taxonomy = Taxonomy()
    for program in labelled_programs(Path("examples/simple/programs")):
        taxa = taxonomy.to_taxa(program.labels)
        if not taxa:
            continue
        width = min(40, max(len(" ".join(map(str, taxon.spans))) for taxon in taxa))
        for (name, spans) in taxa:
            span_string = " ".join(map(couple_to_string, sorted(set(spans))))
            print(f"{span_string:>{width}}\t{name}")

Functions

def is_literal(label_pattern: LabelPattern) ‑> bool

Tell whether a given regular expression pattern is literal, disregarding the dots.

Description

All label patterns of the taxonomy TSV file (second column) will be tested successively. For instance, the label pattern "external_free_call:print" is literal, and then matches only itself. Conversely, the label pattern "internal_free_call:[[:upper:]].*" contains some non-literal characters such as "[" and "*", and then must be compiled into a regular expression. A pattern is considered to be literal if it is equal to its escaped form, not taking the dots into account.

Note

In case not considering the dot as a metacharacter is a problem, it is always possible to force the interpretation of a pattern as non-literal by enclosing it in parentheses.

Expand source code Browse GitHub

def is_literal(label_pattern: LabelPattern) -> bool:
    return label_pattern.replace(".", "\\.") == regex.escape(label_pattern)

def deduplicated_taxa(taxa: List[Taxon]) ‑> List[Taxon]

Remove from the given taxa those that are counted multiple times as prefixes of another ones.

Description

Consider the following program:

1   while n != 1:
2       if n % 2 == 0:
3           n = n // 2
4       else:
5           n = 3 * n + 1

It features exactly one literal integer on lines 1 and 3, and exactly two on lines 2 and 5. Moreover, one of the literals of line 2 is zero. Therefore, the program is originally tagged with the following two couples (among others):

[
    ...
    ("type/number/integer/literal",
        {
            (1, 1): 1,
            (2, 2): 2,
            (3, 3): 1,
            (5, 5): 2,
        }
    ),
    ("type/number/integer/literal/zero", {(2, 2): 1}),
    ...
]

Tip

In the dictionary above, (5, 5): 2 means that the taxon "type/number/integer/literal" has 2 distinct occurrences spanning the lines 5 to 5 (namely, 3 and 1). Such a “counter” dictionary is called a bag, or multiset.

Now, every occurrence of a given taxon is an occurrence of any of its prefix. For instance, an occurrence of the literal integer 0 is obviously an occurrence of a literal integer. Currently, it is counted twice. The purpose of this function is to remove such redundant counts. The longest taxon will be kept, and its prefix count decreased. Finally, the following deduplicated list will be returned:

[
    ...
    ("type/number/integer/literal",
        {
            (1, 1): 1,
            (2, 2): 1, # decremented
            (3, 3): 1,
            (5, 5): 2,
        }
    ),
    ("type/number/integer/literal/zero", {(2, 2): 1}),
    ...
]

Decrementing a span count may result in the deletion of a taxon. For instance, on the same program:

[
    ...
    ("flow/loop", {(1, 5): 1},
    ("flow/loop/exit/late", {(1, 5): 1},
    ("flow/loop/while", {(1, 5): 1},
    ...
]

… becomes after deduplication:

[
    ...
    ("flow/loop/exit/late", {(1, 5): 1},
    ("flow/loop/while", {(1, 5): 1},
    ...
]

Args

taxa : Taxa

A list of couples, sorted lexicographically and consisting of a taxon name and a bag (multiset) of its spans.

Returns

Taxa

The same list, deduplicated.

Expand source code Browse GitHub

def deduplicated_taxa(taxa: Taxa) -> Taxa:
    if len(taxa) < 2:
        return taxa
    for (i, (name, spans)) in enumerate(taxa[1:], 1):
        for (previous_name, previous_spans) in reversed(taxa[:i]):
            # Since `"/"` happens to be a separator in both taxa and Unix-paths, `os.commonpath()`
            # comes in handy for extracting the common prefix of two taxa:
            common_prefix = commonpath((name, previous_name))
            if not common_prefix:
                break
            if previous_name == common_prefix:
                difference = spans - previous_spans
                previous_spans.subtract(spans)
                spans = difference
    result = []
    for (name, spans) in taxa:
        spans += Counter()  # suppress items whose count <= 0
        if spans:  # if any item remains in the bag
            result.append(Taxon(name, spans))
    return result

Classes

class Taxonomy

Expand source code Browse GitHub

class Taxonomy:
    def __init__(
        self,
        taxonomy_path: Optional[Path] = None,
        **kwargs,
    ) -> None:
        taxonomy_path = taxonomy_path or Path(dirname(__file__)) / "resources" / "taxonomy.tsv"
        tsv = taxonomy_path.read_text().partition("-- EOF")[0].strip()
        self.literal_labels: Dict[LabelName, TaxonNames] = defaultdict(list)
        self.compiled_labels: List[Tuple[RegexPattern, TaxonPattern]] = []
        for line in sorted(tsv.split("\n")[1:]):
            (taxon_value, label_value, *_) = line.strip().split(maxsplit=2)
            (taxon_pattern, label_pattern) = (TaxonPattern(taxon_value), LabelPattern(label_value))
            if is_literal(label_pattern):
                self.literal_labels[LabelName(label_pattern)].append(TaxonName(taxon_pattern))
            else:
                self.compiled_labels.append((regex.compile(f"{label_pattern}$"), taxon_pattern))
                # note: "$" is necessary: regex.fullmatch() has no regex.fullsub() counterpart

    @lru_cache(maxsize=None)
    def get_taxon_name_list(
        self, label_name: LabelName, looks_like_a_taxon: Callable = regex.compile(r"^\w+/.+$").match
    ) -> TaxonNames:
        if looks_like_a_taxon(label_name):
            return [TaxonName(label_name)]
        result: TaxonNames = self.literal_labels.get(label_name, [])
        for (label_regex_pattern, taxon_pattern) in self.compiled_labels:
            if label_regex_pattern.match(label_name):
                result.append(TaxonName(label_regex_pattern.sub(taxon_pattern, label_name)))
        return result

    def to_taxa(self, labels: Labels) -> Taxa:
        acc: TaxaSpans = defaultdict(Counter)
        for (label_name, spans) in labels:
            for taxon_name in self.get_taxon_name_list(label_name):
                acc[taxon_name].update(spans)
        taxa = [Taxon(name, spans) for (name, spans) in sorted(acc.items())]
        return deduplicated_taxa(taxa)

Methods

def __init__(self,
taxonomy_path: Union[pathlib.Path, NoneType] = None,
**kwargs
) ‑> NoneType

Read and pre-process the taxonomy specifications.

Args

taxonomy_path : Optional[Path], optional

The path of a two-columns TSV file associating label (search) patterns with taxon (replacement) patterns. For better readability, the taxa are listed on the first column, and the corresponding labels (sometimes very long) on the second column. If not specified, the default taxonomy is used. Defaults to None.

Description

1. Read the taxonomy, falling back to the provided default taxonomy.tsv.
2. Drop the part starting with the string "-- EOF", if any (this pre-processing allows you to leave notes or drafts at the end of the file).
3. Distribute the remaining rows into two different accumulators, depending on the “literality” of the label pattern:
   • self.literal_labels is a dictionary associating every literal label pattern, that it to say, a label name, with a list of taxon names. Most of these lists are singletons, but one can imagine that a unique label name could be associated with multiple taxon names. As a dictionary, it allows O(1) lookups of any given label pattern.
   • self.compiled_labels is a list of couples, of which the first member is a compiled label pattern, and the second member is a replacement pattern which may contain backreferences to one or several capture groups of the label pattern. For instance, it can include the couple (regex.compile(r"index_shape:(\d+)$"), r"subscript/index/shape/\1"), which will be used to “translate” any occurrence of the label name "index_shape:3" into the taxon name "subscript/index/shape/3". As an associative list, it only allows O(n) lookups a given label pattern.

Expand source code Browse GitHub

def __init__(
    self,
    taxonomy_path: Optional[Path] = None,
    **kwargs,
) -> None:
    taxonomy_path = taxonomy_path or Path(dirname(__file__)) / "resources" / "taxonomy.tsv"
    tsv = taxonomy_path.read_text().partition("-- EOF")[0].strip()
    self.literal_labels: Dict[LabelName, TaxonNames] = defaultdict(list)
    self.compiled_labels: List[Tuple[RegexPattern, TaxonPattern]] = []
    for line in sorted(tsv.split("\n")[1:]):
        (taxon_value, label_value, *_) = line.strip().split(maxsplit=2)
        (taxon_pattern, label_pattern) = (TaxonPattern(taxon_value), LabelPattern(label_value))
        if is_literal(label_pattern):
            self.literal_labels[LabelName(label_pattern)].append(TaxonName(taxon_pattern))
        else:
            self.compiled_labels.append((regex.compile(f"{label_pattern}$"), taxon_pattern))

def get_taxon_name_list(self,
label_name: LabelName,
looks_like_a_taxon: Callable = <built-in method match of regex>
) ‑> List[TaxonName]

Translate a label name into a list of taxon names.

Description

First of all, when a label looks like a taxon, it is returned without further ado.

For the rest, most of the work was done during the initialization, by constructing the map self.literal_labels and the list self.compiled_labels. The given label name is first looked up in the map, then matched successively against every regular expression stored in the list.

The second step may be useful even if the first one has already produced one or several translations. For instance, take a taxonomy defining the following associations:

Taxa (replacement patterns)	Labels (search patterns)
call/subroutine/builtin/casting/\1	free_call:(list|dict)
type/sequence/list	free_call:list

Suppose now that we pass the label "free_call:list". The lookup in the map produces a first translation: "type/sequence/list". However, the linear search in the list produces a second translation, namely: "call/subroutine/builtin/casting/list".

>>> a_taxonomy_instance.get_taxon_name_list("free_call:list")
[
    "type/sequence/list",
    "call/subroutine/builtin/casting/list",
]

Therefore, the complexity of this function is linear in every case. However, its memoization avoids having to translate the same label more than one time (cf. lru_cache).

Expand source code Browse GitHub

@lru_cache(maxsize=None)
def get_taxon_name_list(
    self, label_name: LabelName, looks_like_a_taxon: Callable = regex.compile(r"^\w+/.+$").match
) -> TaxonNames:
    if looks_like_a_taxon(label_name):
        return [TaxonName(label_name)]
    result: TaxonNames = self.literal_labels.get(label_name, [])
    for (label_regex_pattern, taxon_pattern) in self.compiled_labels:
        if label_regex_pattern.match(label_name):
            result.append(TaxonName(label_regex_pattern.sub(taxon_pattern, label_name)))
    return result

def to_taxa(self,
labels: List[Label]
) ‑> List[Taxon]

Translate a list of labels to a list of taxa.

Args

labels : Labels

A list of labels, each label consisting in a name and a list of spans.

Returns

Taxa

A sorted list of taxa, each taxon consisting in a name and a bag of spans.

Description

This simple method is the sole entry point of the object. It takes a list of labels, accumulates their translations into taxa (cf. Taxonomy.get_taxon_name_list()) and returns them deduplicated (cf. deduplicated_taxa()).

Expand source code Browse GitHub

def to_taxa(self, labels: Labels) -> Taxa:
    acc: TaxaSpans = defaultdict(Counter)
    for (label_name, spans) in labels:
        for taxon_name in self.get_taxon_name_list(label_name):
            acc[taxon_name].update(spans)
    taxa = [Taxon(name, spans) for (name, spans) in sorted(acc.items())]
    return deduplicated_taxa(taxa)