Pseudo-Pattern zu PCRE-Pattern und best match

[onemorenerd]

Ich baue eine vom Content unabhängige Verwaltung für <title>, <meta name="keywords" ...> und <meta name="description" ...>.
Man muss zu diesen drei Dingen noch einen URL-Pfad angeben, bei dem diese Daten verwendet werden sollen. In diesem Pfad sind ? und * als Platzhalter für ein beliebiges Zeichen bzw. beliebig viele Zeichen erlaubt.

Ich habe also viele Pfade wie

user/*
user/?*/profile
user/?*/profile/*
user/?*/profile/?

und zu jedem ein Set von Title, Keywords und Description.

Bei der Ausgabe im Frontend muss ich den Pfad finden, der am besten zur aktuellen URL passt. Wie stelle ich das am besten an?

Es ist nicht so, dass ich gar keine Idee hätte. Ich sortiere absteigend nach der Länge, ersetze dann "?" durch "[^/]{1}", "*?" und "?*" durch "[^/]{1,}", sowie "*" durch "[^/]*". Die umgeschriebenen Pfade verwende ich in der durch die Sortierung vorgebenen Reihenfolge in preg_match() bis ich einen Treffer habe.
Dieser erste Treffer ist nicht zwangsläufig der einzige oder beste. Zum Beispiel wird die Sortierung das ergeben:

user/?*/profile/*
user/?*/profile/?
user/?*/profile
user/*

Das ist schon nicht optimal. Ich will eigentlich "user/?*/profile/?" zuerst, weil es mir einen längeren Treffer garantiert als "user/?*/profile/*". Deswegen benutze ich eine Callback-Funktion zum Sortieren, die alle "*" entfernt und dann nach Länge entscheidet. Damit ergibt die Sortierung wie gewünscht

user/?*/profile/?
user/?*/profile/*
user/?*/profile
user/*

Nach dem Umschreiben in PCRE-Syntax habe ich

user/[^/]{1,}/profile/[^/]{1}
user/[^/]{1,}/profile/[^/]*
user/[^/]{1,}/profile
 user/[^/]*

Jetzt gehts ans matchen.

$bestMatch = NULL;
foreach ($paths as $path) {
    if (preg_match('§^'. $path .'§', $_SERVER['REQUEST_URI'])) {
        $bestMatch = $path;
        break;
    }
} 

Ist das überhaupt korrekt (Gegenbeispiele, Mehrdeutigkeiten)?
Wie kann ich das besser/effizienter lösen?

[AmicaNoctis]

Sieht imho doch ganz gut aus. Was ich noch machen würde, wäre, vor der Ersetzung der Platzhalter in RegEx noch preg_quote drauf anzuwenden, falls URL-Pfade mal nen Punkt, Klammern oder ein Dollarzeichen enthalten könnten. Die werden nämlich nicht urlencoded. Darüber hinaus enthält $_SERVER["REQUEST_URI"] auch den Query String, der ebenfalls mit einem RegEx-Zeichen anfängt, aber ich weiß nicht, inwiefern GET-Parameter bei deinen URLs überhaupt eine Rolle spielen.

[onemorenerd]

Den Codefetzen habe ich nur mal so aus dem Ärmel geschüttelt, damit klar wird wie ich es meine. Tatsächlich verwende ich preg_quote(). Nur nicht an dieser Stelle sondern früher, in dem Moment wo der Pfad eingegeben wird.

Das wirklich blöde an diesem Problem ist, dass man das Pferd so von hinten aufzäumen muss. Ich will zum Schluß den längsten Treffer. Die Frage ist, welches Pattern ich dafür nehmen muss.

Annahme: Lange Pattern versprechen lange Matches.
Betrachtet man nur die "einfachen" Zeichen in den Pattern, dann stimmt das auch. Aber die "magischen" Zeichen machen Probleme.

Angenommen ich habe die Pfade user/*/foo/bar und user/*/foo/*. Der erste garantiert mir einen längeren Treffer, schon allein weil er mehr "einfache" Zeichen enthält.
Jetzt matche ich das mal mit der URL user/me/foo/bar/baz. Mit dem ersten Pattern ist der Match 15 Zeichen lang. Aber das zweite, kürzere Pattern erzeugt einen längeren Match. Mööp, Annahme widerlegt.

In diesem Beispiel wars einfach, denn ein * am Ende eines Pattern expandiert halt bis zum Ende der URL. Aber das Pattern hätte auch user/*/foo/*z lauten können. Wäre immer noch kürzer als user/*/foo/bar, ich würde immernoch letzterem den Vorzug geben, es würde auch matchen und ich läge wieder daneben.

Ich brauche einen Algorithmus, eine Funktion, die für zwei Pattern ermittelt, welches längere Matches verspricht.
Oder einen anderen Ansatz ...


Übrigens habe ich mich von ? schon verabschiedet und * wird nun durch [^/]{1,} ersetzt. Damit kann man noch alle URLs abdecken, die in dieser Applikation auftreten und es vereinfacht die Implementierung.

[AmicaNoctis]

Es lässt sich einfach nicht ermitteln, welches Pattern den längsten Match verspricht. Du kannst nur die Patterns alle anwenden und alle Matches erfassen und die dann nach Länge ordnen. Oder sehe ich da was falsch?

[onemorenerd]

Naja ich kann zumindest die Anzahl der statischen Zeichen zu Rate ziehen

user/*/foo/bar => 13
user/*/foo/*z => 11

und die Pattern danach sortiert durchprobieren. Sobald ich einen Match habe, kann ich dessen Länge ermitteln und alle Pattern, die weniger statische Zeichen haben als dieser Match, brauche ich gar nicht mehr zu testen.
Damit würde sich sozusagen die Liste der noch testenden Pattern immer weiter verkürzen, je längere Matches sich finden.

[wahsaga]

Angenommen ich habe die Pfade user/*/foo/bar und user/*/foo/*. Der erste garantiert mir einen längeren Treffer, schon allein weil er mehr "einfache" Zeichen enthält.

Du bräuchtest für so einen Fall eine Art KI, die erkennt, dass das erste Muster einen Sonderfall des zweiten darstellt.

Dann könntest du alle "besten" Treffer des zweiten Musters ermitteln (ich nehme an, dass möglicherweise mehr als eine Adresse dieses Kriterium erfüllen kann), und dann unter denen schauen, ob einer davon das spezielle, erste Pattern erfüllt.

Aber das Pattern hätte auch user/*/foo/*z lauten können. Wäre immer noch kürzer als user/*/foo/bar, ich würde immernoch letzterem den Vorzug geben, es würde auch matchen und ich läge wieder daneben.

Aus der Länge eines Patterns auch nur irgendeinen Rückschluss darauf ziehen zu wollen, wie speziell oder allgemein es nun matched, halte ich für ein Ding der Unmöglichkeit.

Ich brauche einen Algorithmus, eine Funktion, die für zwei Pattern ermittelt, welches längere Matches verspricht.

S.o., halte ich für kaum machbar.
In dem Moment, wo du Informationen darüber gewinnen willst, bist du mindestens schon beim Parsen des regulären Ausdrucks, vielleicht schon dabei ihn auf einen bestimmten Text anzuwenden ...

[AmicaNoctis]

die Liste der noch testenden Pattern immer weiter verkürzen, je längere Matches sich finden.

Das klingt sinnvoll.

[mermshaus]

Wenn ich das richtig verstanden habe, sieht die Umformung zum Beispiel so aus:

(pseudo)   user/* <=> user/[^/]{1,}   (PCRE)

Angenommen, ich verhaue mich da jetzt nicht völlig, dürfte der PCRE-Ausdruck keine Unterverzeichnisse matchen. Aber passt das zu dem folgenden Zitat?

Angenommen ich habe die Pfade user/*/foo/bar und user/*/foo/*. Der erste garantiert mir einen längeren Treffer, schon allein weil er mehr "einfache" Zeichen enthält.
Jetzt matche ich das mal mit der URL user/me/foo/bar/baz. Mit dem ersten Pattern ist der Match 15 Zeichen lang. Aber das zweite, kürzere Pattern erzeugt einen längeren Match. Mööp, Annahme widerlegt.

In diesem Beispiel wars einfach, denn ein * am Ende eines Pattern expandiert halt bis zum Ende der URL.

Matcht das Sternchen nun Verzeichnisse?

Und wie passen #5 und #3 zusammen? Im Beispiel in #3 liefert doch das Pattern mit weniger statischen Zeichen das längere Match.

[AmicaNoctis]

Im Beispiel in #3 liefert doch das Pattern mit weniger statischen Zeichen das längere Match.

Du hast vollkommen Recht. Ich nehme mein "Das klingt sinnvoll." beschämt zurück

[onemorenerd]

Nein, bleib mal dabei. Es ist sinnvoll.

@mermshaus: Ich entschuldige mich, bei diesem Beispiel habe ich mich geirrt. Um es klarzustellen: Ein * im Pseudo wird zu [^/]{1,} im PCRE. * matcht also nur bis zum nächsten Slash. Ich überlege sogar, ob * nich generell von einem bis zum nächsten Slash matchen sollte. Aber bisher hätte ich davon keine Vorteile.

Diese Tatsache ist es übrigens auch, die mich auf eine weitere Idee brachte. Dazu komme ich gleich. Vorher noch ein Wort zu

Aus der Länge eines Patterns auch nur irgendeinen Rückschluss darauf ziehen zu wollen, wie speziell oder allgemein es nun matched, halte ich für ein Ding der Unmöglichkeit.

Mir geht es ja nur um ganz spezielle Pattern. So speziell, dass ich glaube, man könnte aus allen Pattern einen Baum konstruieren und mit einer geeigneten Metrik die Güte von Pattern miteinander vergleichen. Aber das ist mir zu kompliziert, vor allem weil sich bestimmte Mehrdeutigkeiten prinzipiell nicht auflösen lassen, soweit ich das sehe.

Nun zu meiner neuen Idee: Sie stützt sich auf die Tatsache, dass * für alles außer / steht. Ich gruppiere alle Pfade nach der Anzahl enthaltener Komponenten, konkret nach substr_count($path, '/').
Vorm Matching bestimme ich die Anzahl der Komponenten in der URL. Und ich brauche schon mal die Pattern(gruppen) alle nicht mehr, die mehr Komponenten haben als die URL. Denn wenn ein Pattern mehr Slashes enthält als das Subject, kann es gar nicht matchen.

Und es kommt noch besser: Sobald ein Pattern aus einer Gruppe matcht, muss ich nur noch diese Gruppe durchprobieren. Alle Pattern aus den anderen Gruppen matchen entweder gar nicht oder kürzer.

Soweit so gut. Jetzt suche ich noch nach einer Möglichkeit, um nicht alle Pattern in einer Gruppe probieren zu müssen. Meine einzige Idee dazu ist ein Präfixbaum.

[AmicaNoctis]

Sobald ein Pattern aus einer Gruppe matcht, muss ich nur noch diese Gruppe durchprobieren. Alle Pattern aus den anderen Gruppen matchen entweder gar nicht oder kürzer.

Dazu müsstest du erstmal klären, was in deinem Falle so eine Gruppe ist und wodurch sie sich auszeichnet.

Das mit dem Präfixbaum (wenn ich es nicht falsch verstehe) ist doch wieder so eine Sache, die sich nicht entscheiden lässt, ohne die konkreten Subjektstrings zu kennen. Es kann ganz zum Schluss immer noch ein */foo/*/bar kommen.

Da es ja um den passendsten Pfad geht und du sinnvollerweise die Anzahl der Komponenten (N) als erstes berücksichtigst, wäre das ein Grund sich ansonsten vom Kriterium der statischen Länge des Patterns zu verabschieden. Damit ist dann vollkommen egal, wieviele konkrete Zeichen ein * matcht, weil es ja trotzdem nur eine von N Pfadkomponenten ist. Dabei gehe ich davon aus, dass Pfadkomponenten atomar sind und nicht unterschiedlich spezifische Einteilungen derselben Basisentität darstellen, z. B.
/ball/
/ball-rot/
/ball-gepunktet/
/ball-rot-gepunktet/
In diesem Fall würde das nicht mehr hinhauen, aber ich gehe mal davon aus, dass du deine Pfadnamen besser gewählt hast.

Wenn du mir bis hier hin zustimmen kannst, bringe ich jetzt noch die Spezifität ins Spiel, wie wir sie aus CSS kennen: Eine *-Komponente ist dabei weniger spezifisch als eine konkret benannte. Nachdem du also alle Patterns aussortiert hast, die eine abweichende Anzahl Komponenten haben, könntest du die übrigen nach substr_count($pattern, "*") sortieren und das erste nach dieser Sortierung matchende Pattern wäre dann der beste Treffer hinsichtlich der Spezifität. Das könnte man dann noch nach Position im Pfad gewichten, so dass z. B. "/*/*/foo/" eine höhere hat als "/bar/*/*/", weil Pfade nach hinten hin ja eh meistens spezieller werden. Damit kannst du wie in CSS ganz allgemein anfangen und dich dann sukzessive zu Sonderfällen vorarbeiten.

[onemorenerd]

Eine Gruppe ist eine Menge von Pseudo-Pattern mit gleicher Anzahl Slashes. Das sieht zum Beispiel so aus:

0 = array('foo', 'x', '*')
1 = array('foo/*', 'foo/bar', 'x/y', 'x/z')
2 = array('foo/*/baz', 'foo/bar/baz', 'x/y/z', 'x/y/*')
4 = array('foo/*/baz/*/foo', 'foo/bar/baz/*/foo', 'x/y/z', 'x/y/*')

Der Präfixbaum für die Gruppe 2 sähe so aus:

<root>
+- foo
|  +- bar - baz
|  `- * - baz
`- x - y
       +- z
       `- *

Wenn ich das Subject x/y/z bekomme, zerlege ich das in die Komponenten x, y und z. Dann wird ausgehend von <root> das Kind x gesucht, von dort aus y und schließlich z.

Würde ich das so umsetzen, bräuchte ich überhaupt keine PCRE mehr. Aber auch wenn ich nur das erste Zeichen jedes Pseudo-Pattern zur Subgruppenbildung benutze, reduziert sich die Zahl der in Frage kommenden Pattern erheblich und es wären maximal zwei Array-Lookups mehr - einer für das erste Zeichen aus dem Subject und falls es keine solche Subgruppe gibt, ein weiterer nach *.

Die Subgruppen sähen so aus:

0 = array(
    'f' => array('foo'),
    'x' => array('x'),
    '*' => array('*'))
1 = array(
    'f' => array('foo/*', 'foo/bar'), 
    'x' => array('x/y', 'x/z'))
...

Für ein Subject aus zwei Komponenten könnte ich die Gruppen 2 und 4 (s.o.) schon komplett ausschließen. Ich beginne also mit Gruppe 1.
Das erste Zeichen des Subject sei ein b. Da es keine Subgruppe b in Gruppe 1 gibt und auch keine Subgruppe *, kann ich Gruppe 1 auschließen und mache weiter mit Gruppe 0.
In Gruppe 0 gibt es ebenfalls keine Subgruppe b, aber eine Subgruppe *.
Ich probiere alle Pattern aus dieser Subgruppe um herauszufinden, welches den längsten Match erzeugt. Weil die Subgruppe nun gerade aus nur einem Pattern besteht, kann ich mir das sogar sparen.

Zumindest für die häufigsten Subjects, nämlich die kurzen, kann ich so mit nur einem substr_count() und ein paar isset() die Anzahl der in Frage kommenden Pattern von einigen hundert auf weniger als ein Dutzend reduzieren.

[onemorenerd]

In diesem Fall würde das nicht mehr hinhauen, aber ich gehe mal davon aus, dass du deine Pfadnamen besser gewählt hast.

Ich wähle die Pfadnamen nicht. Das macht ein Redakteur bzw. sie werden aus Überschriften, Benutzernamen usw. generiert.