# mdgrep – Funktionsweise

Dieses Dokument erklärt, **wie mdgrep innen arbeitet und warum es so gebaut ist**. Für die Benutzung siehe
[BEDIENUNGSANLEITUNG.md](BEDIENUNGSANLEITUNG.md), für Änderungen je Version [CHANGELOG.md](CHANGELOG.md).

Stand: Version 0.1.2

---

## Inhaltsverzeichnis

1. [Überblick](#1-überblick)
2. [Module](#2-module)
3. [Suchsprache: vom Text zum Syntaxbaum](#3-suchsprache-vom-text-zum-syntaxbaum)
4. [Auswertung und Zeitlimit](#4-auswertung-und-zeitlimit)
5. [Hervorhebung und Ausschnitte](#5-hervorhebung-und-ausschnitte)
6. [Markdown-Zerlegung](#6-markdown-zerlegung)
7. [Suchmaschine](#7-suchmaschine)
8. [Web-API und Widget](#8-web-api-und-widget)
9. [Designentscheidungen](#9-designentscheidungen)
10. [Grenzen und Erweiterungsideen](#10-grenzen-und-erweiterungsideen)

---

## 1. Überblick

mdgrep hat **keinen Suchindex**. Alle Texte liegen als *Blöcke* im Speicher; jede Suche prüft jeden Block
(nach Filtern) gegen die übersetzte Suchanfrage. Das ist einfach, unterstützt beliebige reguläre Ausdrücke
und ist bei einigen Megabyte Text schnell genug.

```mermaid
flowchart TB
    subgraph Anfrage
        direction TB
        Q["Suchtext<br/>(rust OR go) -crypto"] --> T[Tokenizer]
        T --> P[Parser]
        P --> AST["Syntaxbaum<br/>And / Or / Not / Term"]
    end
    subgraph Daten
        direction TB
        D["Markdown-Dateien<br/>oder eigene Daten"] --> L["load_markdown()<br/>split_markdown()"]
        L --> B["Blöcke<br/>title, text, meta"]
    end
    AST --> E["SearchEngine.search()"]
    B --> E
    E --> F["Filter"]
    F --> M["Treffer prüfen<br/>(mit Zeitbudget)"]
    M --> S["sortieren, gruppieren,<br/>Seite ausschneiden"]
    S --> H["Fundstellen (Spans)<br/>→ Ausschnitte (Segmente)"]
    H --> R["SearchResult<br/>.to_dict()"]
    R --> CLI["mdgrep<br/>(Terminal)"]
    R --> API["Flask<br/>GET /search"]
    API --> W["Widget<br/>(Browser)"]
```

Drei Begriffe tragen das ganze Design:

| Begriff | Bedeutung |
|---|---|
| **Block** | kleinste durchsuchbare Einheit – ein Absatz, Listenpunkt, Abschnitt, eine Datei oder ein eigener Datensatz. Die logische Verknüpfung gilt *pro Block*. |
| **Span** | Fundstelle als `(start, ende)` im Text eines Blocks |
| **Segment** | Anzeigestück `{"t": Text, "hit": bool}`; eine Liste von Segmenten ergibt den hervorgehobenen Ausschnitt |

---

## 2. Module

| Modul | Aufgabe | Wichtigste Namen |
|---|---|---|
| `query.py` | Suchsprache: Tokenizer, Parser, Auswertung, Fundstellen | `compile_query`, `Query`, `QuerySyntaxError`, `QueryTimeout` |
| `engine.py` | Blöcke halten, filtern, prüfen, sortieren, gruppieren, Seiten | `Block`, `SearchEngine`, `SearchResult`, `Group` |
| `snippets.py` | Fundstellen → Anzeige-Segmente, Kürzen um Treffer | `segments` |
| `markdown.py` | Markdown → Blöcke; Markdown → Klartext | `load_markdown`, `split_markdown`, `markdown_to_text`, `slugify` |
| `cli.py` | Kommandozeile | `main` (Einstieg `mdgrep`) |
| `web.py` | Flask-Blueprint/-App, Entwicklungsserver | `create_blueprint`, `create_app` |
| `static/` | Browser-Widget | `mdgrep-widget.js` (`MdGrep.mount`), `mdgrep-widget.css` |
| `__init__.py` | öffentliche API, `export_static()` | |

Abhängigkeiten zeigen nur in eine Richtung: `engine` nutzt `query` und `snippets`, `markdown` nutzt
`engine` (für `Block`), `cli` und `web` nutzen alles. `query` und `snippets` hängen von nichts im Paket ab.
Nur `web.py` braucht Flask; der Rest kommt mit dem Paket `regex` aus.

---

## 3. Suchsprache: vom Text zum Syntaxbaum

### 3.1 Tokenizer (`_tokenize`)

Der Suchtext wird Zeichen für Zeichen in Tokens zerlegt:

| Zeichen am Token-Anfang | Token |
|---|---|
| Leerraum | wird übersprungen |
| `(` `)` | Klammer |
| `&` / `&&`, `\|` / `\|\|` | `AND` / `OR` |
| `!` | `NOT` |
| `-` **gefolgt von Nicht-Leerraum** | `NOT` (ein einzelnes `-` mit Leerzeichen danach ist ein normales Suchwort) |
| `"` … `"` | Phrase; `\"` steht für ein Anführungszeichen |
| `/` … `/` | regulärer Ausdruck; `\/` wird zu `/`, andere `\x` bleiben erhalten |
| sonst | Wort bis zum nächsten Leerraum, `(`, `)` oder `"` |

Ein Wort, das genau `AND`, `OR`, `NOT`, `UND`, `ODER` oder `NICHT` lautet, wird zum Operator – **nur in
Großbuchstaben**. Weil `-`, `&`, `|`, `!` und `/` nur *am Token-Anfang* Sonderbedeutung haben, bleiben Wörter
wie `e-mail`, `AT&T` oder `TCP/IP` normale Suchwörter.

### 3.2 Parser (rekursiver Abstieg)

```text
query    := or_expr  EOF
or_expr  := and_expr ( OR and_expr )*
and_expr := not_expr ( [AND] not_expr )*      ← AND darf fehlen (Leerzeichen = UND)
not_expr := NOT not_expr | primary
primary  := TERM | "(" or_expr ")"
```

Daraus ergibt sich der Vorrang **NOT > AND > OR**. Ein implizites UND wird erkannt, wenn nach einem Ausdruck
direkt ein Term, eine öffnende Klammer oder ein NOT folgt.

Fehler werden als `QuerySyntaxError(message, position, code)` gemeldet; `position` zeigt auf das Token (bzw. die
öffnende Klammer oder das Textende), `code` ist stabil und übersetzbar (Liste in der Bedienungsanleitung).

Nebenbei merkt sich der Parser für jeden Term, ob er unter einer **ungeraden Anzahl von NOT** steht
(`negated`). Das braucht später die Hervorhebung: `rust -crypto` markiert nur „rust".

### 3.3 Terme werden zu regulären Ausdrücken

| Term | Muster | Beispiel |
|---|---|---|
| Wort | `regex.escape(wort)` | `c++` → `c\+\+` |
| Phrase | Wörter maskiert, verbunden mit `\s+` | `"open source"` → `open\s+source` (trifft auch über Zeilenumbrüche) |
| Regex | unverändert | `/llms?\b/` |

Alle Muster werden mit `IGNORECASE | UNICODE` des PyPI-Moduls **`regex`** kompiliert (Umlaute inklusive).
Ungültige reguläre Ausdrücke fallen schon hier als `invalid_regex` auf – nicht erst bei der Suche.

---

## 4. Auswertung und Zeitlimit

Der Syntaxbaum besteht aus `Term`, `Not`, `And`, `Or`; jeder Knoten hat `evaluate(text, deadline)`.
`And`/`Or` nutzen `all()`/`any()` und brechen daher früh ab.

**Zeitlimit:** Bestimmte reguläre Ausdrücke brauchen exponentiell lange („katastrophales Backtracking",
z. B. `/(a|aa)+$/`). Das Modul `regex` kann jede Suche mit `timeout=` abbrechen. Der Parameter ist aber teuer
(etwa vierfache Laufzeit pro Aufruf), daher:

- **Wörter und Phrasen** laufen **ohne** Zeitlimit – maskierte Literale und `\s+` sind linear, können also nicht
  entarten.
- **Reguläre Ausdrücke** bekommen als Zeitlimit die Restzeit bis zur Frist (`deadline`).
- `Query.matches()` prüft die Frist **einmal pro Aufruf**; ist sie abgelaufen, folgt `QueryTimeout`.

Die Suchmaschine setzt eine Frist für die ganze Suche (`time_budget`). Läuft sie ab, endet die Schleife und
das Ergebnis trägt `truncated = True` – der Server bleibt erreichbar, der Nutzer bekommt ein Teilergebnis.

---

## 5. Hervorhebung und Ausschnitte

**Fundstellen (`Query.spans`)**: Für jeden *positiven* Term (nicht unter NOT) werden alle Treffer gesucht,
Treffer der Länge 0 (z. B. von `/x*/`) verworfen, dann sortiert und überlappende oder angrenzende Bereiche
zusammengefasst. Aus `open OR source` auf „open source" werden so zwei getrennte Markierungen, aus
`abc OR bcd` auf „abcd" eine durchgehende.

**Ausschnitte (`snippets.segments`)**: Ist der Text kürzer als `max_chars`, wird er komplett in Segmente
zerlegt. Sonst:

1. Um jede Fundstelle wird ein Fenster von `context` Zeichen gelegt.
2. Fensterränder werden an Wortgrenzen verschoben (höchstens 20 Zeichen weit), damit keine Wörter zerschnitten
   werden.
3. Überlappende Fenster verschmelzen.
4. Fenster werden aufgenommen, solange das Budget `max_chars` reicht – das **erste Fenster immer**, damit
   mindestens ein Treffer sichtbar ist.
5. Lücken und abgeschnittene Enden werden durch `" … "` markiert.

Ohne Fundstelle im Text (Treffer nur im Titel) wird der Textanfang gezeigt.

---

## 6. Markdown-Zerlegung

`split_markdown()` arbeitet **zeilenbasiert** mit einem kleinen Scanner, nicht mit einem vollständigen
Markdown-Parser. Der Scanner liefert je Zeile: Index, Inhalt, „in Code-Block?" und ggf. die erkannte
Überschrift (`#` bis `######`). Zeilen innerhalb von Code-Blöcken (` ``` ` oder `~~~`) werden nie als
Überschrift oder Listenpunkt gedeutet.

| Modus | Regel |
|---|---|
| `file` | eine Datei = ein Block; Titel = erste Überschrift |
| `heading` | neuer Block bei jeder Überschrift; Titel = Überschrift, Anker = `slugify(Überschrift)` |
| `paragraph` | neuer Block nach jeder Leerzeile (außerhalb von Code-Blöcken); Trennlinien werden übersprungen |
| `list` | neuer Block bei jedem Listenpunkt der obersten Ebene; eingerückte Zeilen und Zeilen direkt darunter („lazy continuation") gehören dazu; Text außerhalb von Listen wird zu Absatz-Blöcken; Trennlinien und Überschriften beenden einen Block |

**Dialekte** (nur Modus `list`): Markdown-Renderer zerlegen Listen unterschiedlich. Damit Blöcke zu den
Elementen im gerenderten HTML passen (wichtig für Sprungmarken), gibt es zwei Regelsätze:

| | `commonmark` | `python-markdown` |
|---|---|---|
| Listenmarker | `-` `*` `+` `1.` `1)` am Zeilenanfang | dazu bis zu 3 Leerzeichen Einrückung; nummeriert nur `1.` |
| Liste direkt unter einer Absatzzeile | beginnt eine Liste | gehört zum Absatz |

Jeder Block bekommt `meta["section"]` (letzte Überschrift darüber), `meta["kind"]` und `meta["markdown"]`
(Originaltext), dazu `source`, `line` und `id = "<source>:<line>"`.

**Markdown → Klartext** (`markdown_to_text`): pro Zeile werden Listen-, Zitat- und Überschriftenmarker entfernt,
Bilder durch ihren Alternativtext, Links durch ihren Linktext ersetzt, Inline-Code, Fett, Kursiv und
Durchgestrichen ausgepackt (Unterstriche nur an Wortgrenzen, damit `snake_case` erhalten bleibt). Zeilen
bleiben erhalten, mehrere Leerzeilen werden zu einer. Durchsucht und angezeigt wird dieser Klartext.

In den Modi `file` und `heading` wird der Titel vom Textanfang entfernt, damit er im Ergebnis nicht doppelt
erscheint.

---

## 7. Suchmaschine

### 7.1 Laden

`SearchEngine(quelle, reload_check=…, reload_interval=…)` nimmt eine Liste von Blöcken oder eine Funktion, die
sie liefert. Beim Laden wird für jeden Block der **Suchtext** `titel + "\n" + text` einmal vorberechnet –
Titel und Text werden gemeinsam durchsucht, aber getrennt angezeigt.

**Neuladen:** Mit Ladefunktion und `reload_check` (liefert einen beliebigen vergleichbaren Wert, etwa
Dateianzahl und neueste Änderungszeit) prüft die Suchmaschine höchstens alle `reload_interval` Sekunden, ob
sich der Wert geändert hat, und lädt dann neu. Blöcke und Suchtexte werden zusammen als ein Tupel ersetzt –
laufende Suchen sehen immer einen konsistenten Stand.

### 7.2 Ablauf von `search()`

```mermaid
flowchart TD
    A["Anfrage kompilieren<br/>(oder fertige Query)"] --> B["Frist = jetzt + time_budget"]
    B --> C["ggf. neu laden"]
    C --> D{"für jeden Block"}
    D -->|"Filter / Prädikat passen nicht"| D
    D -->|passt| E{"query.matches()"}
    E -->|ja| F[in Trefferliste]
    E -->|nein| D
    E -->|QueryTimeout| G["truncated = True,<br/>Schleife beenden"]
    F --> D
    D -->|fertig| H["sortieren (sort_key, reverse)"]
    G --> H
    H --> I["gruppieren (group_by)<br/>Reihenfolge = erster Treffer je Gruppe"]
    I --> J["Seite: Gruppen offset … offset+limit"]
    J --> K["nur für die Seite:<br/>Spans + Segmente des ersten Blocks je Gruppe"]
    K --> L[SearchResult]
```

Wichtige Details:

- **Filter** vergleichen `block.meta[schlüssel]` mit einem Wert oder einer Menge von Werten; leere Werte werden
  ignoriert.
- **Gruppierung**: `group_by(block)` liefert einen Schlüssel oder `None` (= eigene Gruppe). Weil vorher sortiert
  wird, ist der erste Block einer Gruppe der „beste" (z. B. neueste); die übrigen landen in `also`.
- **Seiten** zählen Gruppen, nicht Blöcke. `next_offset` ist `None`, wenn keine weitere Seite existiert.
- **Teure Arbeit nur für die sichtbare Seite**: Fundstellen und Ausschnitte werden nur für die bis zu
  `limit` angezeigten Gruppen berechnet, nicht für alle Treffer.

---

## 8. Web-API und Widget

### 8.1 Web-API (`web.py`)

`create_blueprint()` registriert `GET /search` und liefert die Widget-Dateien unter `/mdgrep-static/` aus.
Ablauf einer Anfrage: Parameter lesen und begrenzen (`offset ≥ 0`, `1 ≤ limit ≤ max_limit`, Länge der
Anfrage) → Filter-Parameter übernehmen (leer/`all` = keine Einschränkung, `a,b` = mehrere Werte) →
`engine.search()` → interne Metadaten (`hide_meta`, Standard `markdown`) entfernen → JSON.
`QuerySyntaxError` wird zu HTTP 400 mit `{"error": {code, message, position}}`.

`create_app()` baut eine eigenständige Flask-App (Unicode im JSON nicht maskiert) und kann zusätzlich ein
Verzeichnis statisch ausliefern; `send_from_directory` verhindert dabei Zugriffe außerhalb dieses Verzeichnisses.

### 8.2 Widget (`static/mdgrep-widget.js`)

Ein einzelnes Skript ohne Abhängigkeiten, das `window.MdGrep = {mount, labels, version}` bereitstellt.

```mermaid
sequenceDiagram
    participant U as Nutzer
    participant W as Widget
    participant A as API
    U->>W: tippt „rust -cr"
    Note over W: Debounce 300 ms – nichts senden
    U->>W: tippt „ypto"
    W->>W: URL aktualisieren (?q=…)
    W->>A: GET search?q=rust -crypto (AbortController #1)
    U->>W: ändert Filter „Sprache"
    W->>A: Anfrage #1 abbrechen, GET … &lang=de (#2)
    A-->>W: JSON #2
    W->>W: Kästchen per createElement/textContent bauen
    W-->>U: Ergebnisse, Statuszeile
```

- **Zustand in der URL** (`history.replaceState`): Suchbegriff und Filter stehen in `?q=…&lang=…`; beim Laden
  liest das Widget sie wieder ein und sucht sofort. Dadurch sind Suchen teilbar, und die Zurück-Taste aus einem
  geöffneten Treffer stellt die Suche wieder her.
- **Veraltete Antworten** werden doppelt abgefangen: `AbortController` bricht die alte Anfrage ab, und eine
  Antwort wird nur angezeigt, wenn sie zur zuletzt gestarteten Anfrage gehört.
- **Sicherheit:** Alle Texte aus der Antwort werden mit `textContent` bzw. als Textknoten eingefügt, `<mark>`
  entsteht per `createElement`. HTML aus Dokumenten wird so nie ausgeführt.
- **Fehler:** HTTP 400 → übersetzte Meldung zum `code` plus Position; 429 → „zu viele Anfragen"; sonst
  allgemeine Meldung.
- **Gestaltung:** nur Klassen `mdgrep-*` und CSS-Variablen `--mdgrep-*` mit Standardwerten als Fallback;
  `[hidden]` wird mit `!important` erzwungen, damit Seiten-CSS ausgeblendete Elemente nicht wieder einblendet.
- **Ohne Skriptcode:** Elemente mit `data-mdgrep` werden beim Laden automatisch eingerichtet.

---

## 9. Designentscheidungen

| Entscheidung | Verworfene Alternativen | Grund |
|---|---|---|
| **Kein Index – Volltext-Scan im Speicher** | Whoosh, SQLite FTS, Elasticsearch | Reguläre Ausdrücke lassen sich ohnehin nicht über einen Wortindex beantworten; Whoosh ist seit 2016 ungepflegt; bei einigen MB Text ist der Scan schnell genug (≈ 30–150 ms bei 15 MB) und es gibt nichts zu synchronisieren. |
| **PyPI-`regex` statt `re`** | Standardmodul `re` | Nur `regex` kann eine laufende Suche per `timeout=` abbrechen – Voraussetzung, um Nutzer-Regex auf einem Server zu erlauben. |
| **Zeitlimit nur für Regex-Terme** | Zeitlimit für alle Terme | Der Timeout-Parameter vervierfacht die Kosten pro Aufruf; Wörter und Phrasen können nicht entarten. Zusammen mit den vorberechneten Suchtexten gemessen 4–9× schnellere Suchen (Version 0.1.1). |
| **Logik pro Block** | pro Datei, pro Satz | Datei ist zu grob (`a AND b` trifft fast immer), Satz zu fein; der Split-Modus lässt den Nutzer die passende Einheit wählen. |
| **Titel und Text getrennt** | Titel als erste Textzeile | Sonst erscheint der Titel im Ergebnis doppelt; Programme mit eigenen Daten können einen echten Titel setzen. |
| **Zeilenbasierter Markdown-Zerleger** | vollständiger Markdown-Parser (z. B. markdown-it) | Für Blockgrenzen genügt ein kleiner Scanner, keine zusätzliche Abhängigkeit; Abweichungen einzelner Renderer deckt die `dialect`-Option ab. |
| **`dialect`-Option** | eine feste Regel | Sprungmarken funktionieren nur, wenn Blöcke exakt den HTML-Elementen des Renderers entsprechen; CommonMark und Python-Markdown unterscheiden sich bei Listen messbar (im hnews-Archiv zwei Fehlerbilder in 70 bzw. 197 Dateien). |
| **`relative_to`** | absolute Pfade | Eine Web-API soll keine Serverpfade preisgeben. |
| **Stabile Fehlercodes** | nur Fehlermeldungstext | Oberflächen können Meldungen übersetzen (Widget: de/en), ohne Texte zu parsen. |
| **Widget ohne Framework, nur `textContent`** | React/Vue, `innerHTML` | Läuft in jeder Seite, keine Build-Kette, keine XSS-Lücke durch Dokumentinhalte. |
| **Eigenes Repository, Installation per Git-Tag** | PyPI, Unterordner eines Projekts | Wiederverwendbar in beliebigen Projekten, unabhängig versioniert, ohne Veröffentlichung auf PyPI. |
| **MIT-Lizenz** | GPL | Einfache Wiederverwendung, auch in fremden Projekten. |

---

## 10. Grenzen und Erweiterungsideen

| Grenze | Auswirkung | Mögliche Erweiterung |
|---|---|---|
| Linearer Scan | Laufzeit wächst mit der Textmenge; bei Hunderten MB zu langsam | Vorfilter mit Trigramm-Index für Wörter/Phrasen |
| Jeder Server-Worker hält alle Blöcke | ca. 90 MB pro Worker bei 15 MB Markdown | gemeinsamer Speicher oder Index auf Platte |
| Keine Wortstämme | „Haus" findet nicht „Häuser" | optionale Stemming-Stufe (z. B. Snowball) |
| Keine Relevanz-Sortierung | Reihenfolge nur nach `sort_key` | Score aus Trefferzahl/Position |
| Doppelte Überschriften | `slugify` hängt kein `-1`, `-2` an (anders als GitHub) | Zähler je Datei wie GitHub |
| Nur ATX-Überschriften (`#`) | Setext-Überschriften (unterstrichen mit `===`/`---`) werden nicht erkannt | Scanner erweitern |
| Operatoren nur in Großbuchstaben | `and` ist ein Suchwort | bewusst so; ggf. Option |
| Titel und Text gemeinsam durchsucht | eine Phrase kann theoretisch über die Grenze Titel/Text hinweg treffen | Grenzzeichen statt Zeilenumbruch |