#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
idioma_sortes_generateur.py — Générateurs énumérant tous les termes
d'un système de langages algébriques multi-sortes.

Le système est présenté comme pour la reconnaissance :

    L = <a, b, f(H), g(H,L)>
    H = <e, j(H,H), k(H,L,H)>

Les automates  { |--a, |--b, |--f(H), |--g(H,L) }  et
{ |--e, |--j(H,H), |--k(H,L,H) }  sont ici parcourus en GÉNÉRATION :
toutes les règles de production sont explorées, chaque position
d'argument devenant un appel récursif du générateur du langage
désigné à cette position — les générateurs sont donc mutuellement
récursifs, comme les automates dont ils proviennent.

Le parcours reste stratifié par taille (nombre d'opérateurs, toutes
sortes confondues) : l'énumération est équitable, chaque terme de
chaque langage apparaît au bout d'un temps fini, une seule fois.
"""

import re
from itertools import product


# ----------------------------------------------------------------------
#  1. Analyse d'un système de présentations
# ----------------------------------------------------------------------

def analyse_presentation(presentation: str):
    """
    Analyse "L = <a, b, f(H), g(H,L)>" et retourne le couple
    (nom_du_langage, {opérateur: profil}), le profil étant le tuple
    des langages attendus aux positions d'argument. Le point "."
    désigne le langage en cours de définition.
    """
    m = re.match(r"\s*([A-Za-z_][A-Za-z_0-9]*)\s*=\s*<(.*)>\s*$",
                 presentation, re.DOTALL)
    if not m:
        raise ValueError(f"Présentation illisible : {presentation!r}")
    langage, interieur = m.group(1), m.group(2)

    motif = re.compile(
        r"([A-Za-z_][A-Za-z_0-9]*)\s*"
        r"(\(\s*([A-Za-z_][A-Za-z_0-9]*|\.)"
        r"(\s*,\s*([A-Za-z_][A-Za-z_0-9]*|\.))*\s*\))?")

    signature = {}
    pos = 0
    while pos < len(interieur):
        while pos < len(interieur) and interieur[pos] in " ,\t\n":
            pos += 1
        if pos >= len(interieur):
            break
        m = motif.match(interieur, pos)
        if not m:
            raise ValueError(f"Générateur illisible à partir de : "
                             f"{interieur[pos:]!r}")
        operateur = m.group(1)
        if m.group(2) is None:
            profil = ()
        else:
            args = re.findall(r"[A-Za-z_][A-Za-z_0-9]*|\.", m.group(2))
            profil = tuple(langage if arg == "." else arg for arg in args)
        if operateur in signature and signature[operateur] != profil:
            raise ValueError(f"L'opérateur {langage}.{operateur} est "
                             f"déclaré avec deux profils.")
        signature[operateur] = profil
        pos = m.end()
    if not signature:
        raise ValueError(f"Le langage {langage} n'a aucun générateur.")
    return langage, signature


def analyse_systeme(*presentations):
    """
    Analyse un système de présentations, vérifie que tout langage
    mentionné est défini et que chaque langage est habité.
    Retourne { langage : { opérateur : profil } }.
    """
    systeme = {}
    for p in presentations:
        langage, signature = analyse_presentation(p)
        if langage in systeme:
            raise ValueError(f"Le langage {langage} est présenté deux fois.")
        systeme[langage] = signature

    for langage, signature in systeme.items():
        for operateur, profil in signature.items():
            for arg in profil:
                if arg not in systeme:
                    raise ValueError(
                        f"{langage}.{operateur} attend un terme du langage "
                        f"{arg!r}, qui n'est pas défini dans le système.")

    habites = set()
    progres = True
    while progres:
        progres = False
        for langage, signature in systeme.items():
            if langage in habites:
                continue
            for profil in signature.values():
                if all(arg in habites for arg in profil):
                    habites.add(langage)
                    progres = True
                    break
    vides = set(systeme) - habites
    if vides:
        raise ValueError(f"Langage(s) vide(s), aucun terme constructible : "
                         f"{sorted(vides)}")
    return systeme


# ----------------------------------------------------------------------
#  2. Compositions d'un entier
# ----------------------------------------------------------------------

def compositions(n: int, k: int):
    """
    Énumère les k-uplets (n1, ..., nk) d'entiers >= 1 de somme n :
    les répartitions d'un budget n entre k positions d'argument.
    """
    if k == 1:
        if n >= 1:
            yield (n,)
        return
    for premier in range(1, n - k + 2):
        for reste in compositions(n - premier, k - 1):
            yield (premier,) + reste


# ----------------------------------------------------------------------
#  3. Le système de générateurs mutuellement récursifs
# ----------------------------------------------------------------------

class GenerateurSortes:
    """
    Système de générateurs énumérant les termes de chaque langage
    d'un système multi-sortes, par taille croissante.

    `termes(langage, n)` parcourt les règles de production du
    langage :
      - une règle |--s de constante produit s si n == 1 ;
      - une règle |--s(S1, ..., Sk) répartit le budget n-1 entre les
        k positions, la position i étant un appel récursif
        `termes(Si, ni)` du générateur du langage attendu à cette
        position ; les sous-termes sont combinés par produit
        cartésien.

    Les générateurs des différents langages s'appellent ainsi
    mutuellement, exactement comme les automates reconnaisseurs.
    """

    def __init__(self, systeme: dict):
        self.systeme = {lg: dict(sig) for lg, sig in systeme.items()}
        self._strates = {}                 # mémo : (langage, taille) -> termes

    # -- une strate : les termes du langage, de taille exactement n ------------
    def termes(self, langage: str, n: int) -> list:
        """Liste des termes du langage `langage` de taille exactement n."""
        if langage not in self.systeme:
            raise ValueError(f"Langage inconnu : {langage!r}")
        if n < 1:
            return []
        if (langage, n) in self._strates:
            return self._strates[(langage, n)]

        strate = []
        for operateur, profil in self.systeme[langage].items():
            if not profil:                              # règle |--s
                if n == 1:
                    strate.append(operateur)
            else:                                       # règle |--s(S1,...,Sk)
                for repartition in compositions(n - 1, len(profil)):
                    sous_termes = [self.termes(arg, ni)  # appels récursifs des
                                   for arg, ni           # générateurs désignés
                                   in zip(profil, repartition)]
                    for choix in product(*sous_termes):
                        strate.append(f"{operateur}({','.join(choix)})")

        self._strates[(langage, n)] = strate
        return strate

    # -- énumération du langage entier -------------------------------------------
    def iter(self, langage: str):
        """Énumère tous les termes du langage, par taille croissante."""
        n = 1
        while True:
            for terme in self.termes(langage, n):
                yield terme
            n += 1

    def premiers(self, langage: str, m: int) -> list:
        """Les m premiers termes de l'énumération du langage."""
        resultat = []
        for terme in self.iter(langage):
            resultat.append(terme)
            if len(resultat) == m:
                return resultat
        return resultat

    def compte(self, langage: str, n: int) -> int:
        """Nombre de termes du langage de taille exactement n."""
        return len(self.termes(langage, n))

    def __repr__(self):
        lignes = []
        for langage, signature in self.systeme.items():
            regles = ", ".join(
                f"|--{op}" if not profil else f"|--{op}({','.join(profil)})"
                for op, profil in signature.items())
            lignes.append(f"générateur {langage} : {{{regles}}}")
        return "\n".join(lignes)


# ----------------------------------------------------------------------
#  4. La fonction demandée
# ----------------------------------------------------------------------

def idioma_sortes_generateur(*presentations) -> GenerateurSortes:
    """
    Construit le système de générateurs mutuellement récursifs
    énumérant les termes de chaque langage du système.

    >>> G = idioma_sortes_generateur("L = <a,b,f(H), g(H,L)>",
    ...                              "H = <e, j(H,H),k(H,L,H)>")
    >>> G.premiers("L", 5)
    ['a', 'b', 'f(e)', 'g(e,a)', 'g(e,b)']
    """
    return GenerateurSortes(analyse_systeme(*presentations))


# ----------------------------------------------------------------------
#  5. Programme principal
# ----------------------------------------------------------------------

SYNOPSIS = """
======================================================================
 idioma_sortes_generateur — énumération des termes d'un système de
                            langages multi-sortes
======================================================================
 Le système est présenté comme pour la reconnaissance :

     L = <a, b, f(H), g(H,L)>
     H = <e, j(H,H), k(H,L,H)>

 Les automates sont parcourus en génération : toutes les règles de
 production sont explorées, chaque position d'argument étant un
 appel récursif du générateur du langage désigné à cette position.
 Les générateurs sont donc mutuellement récursifs, comme les
 automates dont ils proviennent.

 L'énumération est stratifiée par taille : chaque terme de chaque
 langage apparaît une fois et une seule, au bout d'un temps fini.

 idioma_sortes_generateur(présentation1, ...) retourne le système G :
    - for t in G.iter("L") : ...   énumère le langage L entier ;
    - G.termes("L", n)             termes de L de taille n ;
    - G.premiers("L", m)           les m premiers termes de L ;
    - G.compte("L", n)             nombre de termes de L de taille n.
======================================================================
"""

if __name__ == "__main__":
    print(SYNOPSIS)

    presentations = ("L = <a,b,f(H), g(H,L)>",
                     "H = <e, j(H,H),k(H,L,H)>")
    for p in presentations:
        print(f"Présentation : {p}")
    G = idioma_sortes_generateur(*presentations)
    print(f"\n{G}\n")

    for langage in ("L", "H"):
        print(f"Les 12 premiers termes de {langage} :")
        for terme in G.premiers(langage, 12):
            print(f"   {terme}")
        print()

    print("Nombre de termes par taille :")
    print("   taille : " + "  ".join(f"{n:>6}" for n in range(1, 9)))
    for langage in ("L", "H"):
        comptes = "  ".join(f"{G.compte(langage, n):>6}" for n in range(1, 9))
        print(f"   {langage}      : {comptes}")

    # -- contrôle de cohérence avec le système d'automates reconnaisseurs -------
    print("\nContrôle de cohérence avec les automates reconnaisseurs :")
    try:
        from idioma_sortes import idioma_sortes
        S = idioma_sortes(*presentations)
        tout_va = True
        for langage in ("L", "H"):
            engendres = G.premiers(langage, 200)
            tout_va &= all(S(langage, t) for t in engendres)
            # contre-épreuve : un terme de L ne doit pas être reconnu dans H
            autre = "H" if langage == "L" else "L"
            tout_va &= not any(S(autre, t) for t in engendres[:50])
        print(f"   200 termes de chaque langage engendrés et reconnus dans "
              f"leur langage,\n   jamais dans l'autre : {tout_va}")
    except ImportError:
        print("   (idioma_sortes.py absent : contrôle sauté)")