[PHP] Topological sorting

[Agape]

Ciao a tutti. Ho un quesito un po' complesso.

Sto facendo un framework, una sorta di cms in php e mi sono fermato al caricamento dei plugin. Il quesito è il seguente:

Dato che ogni plugin può estendere il core (il cms stesso) oppure un altro plugin ci deve essere un ordine nel caricamento dei plugin.

Mi spiego meglio. Il plugin A estende le funzionalità del plugin B che estende a sua volta il core. Ora se io carico prima il plugin A e successivamente il plugin B succede un casino, perché A non trova B nel momento in cui viene caricato. La risposta al problema sembra essere il topological sorting. Questo algoritmo permette di ordinare i nodi del grafo in modo tale per cui i nodi che stanno più in alto vengono messi per primi nell'ordinamento.

Bhe spero di essermi spiegato. Su wikipedia c'è lo pseudocodice ma non sono in grado di scriverlo in php anche perché non riesco a capire alcune parti. Se qualcuno ha una minima idea di come fare si faccia avanti! grazie

[Grino]

Fammi capire, ma tu memorizzi ciò che devi caricare in un grafo orientato non ciclico?

Se A ha bisogno di B, si farà carico di effettuare la sua require_once. Se B ha bisogno di Core farà le sue require_once.

Se non ti piace l'utilizzo diretto delle raquire_once, e vuoi nasconderle nel core, allora il plugin (per dire) dovrà comunque caricare un elemento base (comune a tutti i plugin) che permetta loro di dichiarare al core la propria esistenza e dipendenze, di modo che il core possa elaborare il nome simbolico del plugin in un nome di file, cosa che farà anche per le dipendenze, e caricare con i file necessari con proprie require_once.

[Agape]

Si ammetto che sono stato un po vago. Dunque...il sistema è simile a quello di wordpress o drupal..

I plugin risiedono dentro la cartella plugins e a loro volta dentro un'altra cartella chiamata col nome del plugin. Il sistema verifica ogni volta quali plugin sono presenti all'interno di quella cartella e memorizza nel database le informazioni dei plugin nuovi. Tra le informazioni ci sono appunto il nome del plugin e le sue dipendenze (quindi quello che va ad estendere, se il plugin estende il core non serve specificarlo mentre se estende un altro plugin è obbligatorio specificarlo).

All'interno dei plugin possono essere richiamate due funzioni:

- add_hook che aggiunge un punto di aggancio nel caso in cui altri plugin vogliano estenderlo in quel punto
- add_action che specifica quale hook richiamare e quale funzione all'interno del plugin richiamare per quell'hook

Ora il problema è il seguente: se l'unica cosa che può essere estesa fosse il core allora basterebbe caricare tutti i plugin con un ciclo while dal database. Ma dato che plugin possono estendere altri plugin allora nel caricamento deve esserci un ordine..prima i plugin estesi e poi i plugin che estendono. Si forma quindi un grafo di dipendenze dove solo, diciamo così, i figli sanno chi sono i padri (non i nonni). Qui dovrebbe venirmi in aiuto questo algoritmo che ho citato. Spero di essere stato più chiaro!

[EDIT]: in questo link c'è uno pseudocodice che sembra più chiaro di quello di wikipedia: http://www.patrickdewane.com/2009/03...ical-sort.html

[Grino]

Il sistema verifica ogni volta quali plugin sono presenti all'interno di quella cartella e memorizza nel database le informazioni dei plugin nuovi.Tra le informazioni ci sono appunto il nome del plugin e le sue dipendenze (quindi quello che va ad estendere, se il plugin estende il core non serve specificarlo mentre se estende un altro plugin è obbligatorio specificarlo).

Prima osservazione; se il sistema verifica ogni volta i plugin presenti, perchè non sfrutti il file system come base dati invece di trasferire in un DB, e poi dal DB effettuare le operazioni. Se invece ritieni che il DB possa essere più veloce nel restituire le informazioni, forse sarebbe opportuno implementare un sistema di caricamento dei plugin, che li posiziona in modo opportuno nel file system e ne carica le informazioni in un DB,oltre ad un sistema di rimozione dei plug che li rimuove dal file system e dal DB, ovviamente dopo aver verificato che il plugin che si tenta di rimuovere non sia dipendenza per un altro ancora attivo.

Seconda osservazione;dato che non hai realmente un grafo, anche potendo immaginare che sia tale, ma hai una struttura lineare data dal DB con dei riferimenti ad altri elementi, puoi semplificarti la vita facendo delle chiamate ricorsive. Se vuoi un abbozzo di codice vorrei sapere che informazioni memorizzi nel DB dei plugin e come ottieni il nome file contenente il plugin completo di percorso.

[Agape]

Originariamente inviato da Grino
Prima osservazione; se il sistema verifica ogni volta i plugin presenti, perchè non sfrutti il file system come base dati invece di trasferire in un DB, e poi dal DB effettuare le operazioni. Se invece ritieni che il DB possa essere più veloce nel restituire le informazioni, forse sarebbe opportuno implementare un sistema di caricamento dei plugin, che li posiziona in modo opportuno nel file system e ne carica le informazioni in un DB,oltre ad un sistema di rimozione dei plug che li rimuove dal file system e dal DB, ovviamente dopo aver verificato che il plugin che si tenta di rimuovere non sia dipendenza per un altro ancora attivo.

Il database lo uso perché un plugin può essere installato ma non attivo e questa informazione è presente nel database.

Seconda osservazione;dato che non hai realmente un grafo, anche potendo immaginare che sia tale, ma hai una struttura lineare data dal DB con dei riferimenti ad altri elementi, puoi semplificarti la vita facendo delle chiamate ricorsive. Se vuoi un abbozzo di codice vorrei sapere che informazioni memorizzi nel DB dei plugin e come ottieni il nome file contenente il plugin completo di percorso.

Il database è questo:

-- phpMyAdmin SQL Dump
-- version 3.3.9
-- http://www.phpmyadmin.net
--
-- Host: localhost
-- Generato il: 23 gen, 2011 at 10:54 AM
-- Versione MySQL: 5.1.52
-- Versione PHP: 5.3.5

SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";

--
-- Database: `cmf_test`
--

-- --------------------------------------------------------

--
-- Struttura della tabella `plugins`
--

CREATE TABLE IF NOT EXISTS `plugins` (
  `flatname` varchar(50) NOT NULL,
  `name` varchar(50) NOT NULL,
  `version_name` varchar(40) NOT NULL,
  `version_number` int(15) NOT NULL,
  `description` text NOT NULL,
  `dependencies` text NOT NULL,
  `active` int(1) NOT NULL,
  PRIMARY KEY (`flatname`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

--
-- Dump dei dati per la tabella `plugins`
--

INSERT INTO `plugins` (`flatname`, `name`, `version_name`, `version_number`, `description`, `dependencies`, `active`) VALUES
('A', '', '', 0, '', '', 1),
('B', '', '', 0, '', '["A"]', 1),
('C', '', '', 0, '', '["A"]', 1),
('D', '', '', 0, '', '["K"]', 1),
('E', '', '', 0, '', '["B"]', 1),
('F', '', '', 0, '', '["C","K"]', 1),
('K', '', '', 0, '', '', 1);

nell'insert c'è un esempio. Per quanto riguarda il campo dependencies l'ho fatto in json come array così è più semplice da php estrarlo con json_decode. La struttura de FS è in allegato. grazie

[EDIT] dimenticavo, la struttura di users.plugin è:

flatname: users
name: Users
version: 0.0.1-alpha-rel
description: null
dependencies: plugin1, plugin2

però usando il database questa parte non serve leggerla da qui, per il suo caricamento riesco a farlo io grazie

[EDIT2]
questa è la struttura che ho già fatto, non è altro che la query al database di tutti i plugin attivi

function initialize_plugins() {
    global $db;
    
     $sql = "SELECT flatname, dependencies FROM plugins WHERE active='1'";
     foreach ($db->query($sql) as $row) {
         $dependencies[$row['flatname']] = json_decode($row['dependencies']);
         
    }
         var_dump($dependencies);
} 

[Grino]

$pluginsDipendenze=array();
$pluginsCaricati=array();

function CaricaPlugin($nome,$dipendenze){
    global $pluginsCaricati,$pluginsDipendenze;
    
    //se un plugin è già caricato è inutile ricaricarlo
    if(!isset($pluginsCaricati[$nome])){
        //prima carico i plugin da cui dipende
        foreach($dipendenze as $nomePluginDip)
            CaricaPlugin($nomePluginDip,$pluginsDipendenze[$nomePluginDip]);
        
        //quindi carico il plugin e aggiorno l'elenco dei pluin già caricati
        //sistema il percorso a dovere perchè non so dove piazzi questa funzione
        require_once "/plugin/$nome/$nome.plugin";
        $pluginsCaricati[$nome]=true;//qui potresti voler assegnare la versione o altri dati più interessanti
    }
}

function initialize_plugins(){
    global $pluginsDipendenze,$db;
    
    //qui fai le require_one di base del core se ne hai
    
    $sql="select flatname, dependecies from plugins where active=1";
    foreach($db->query($sql) as $plugin)
        $pluginsDipendenze[$plugin['flatname']] = json_decode($plugin['dependencies']);
    //le righe sopra forse vanno bene o forse no. A me serve che ogni
    //$pluginsDipendenze[$plugin['flatname']]contenga o array(), ovvero un array php
    //vuoto, o un array con i flatname dei plugin da cui dipende
    
    foreach($pluginsDipendenze as $nome=>$dipendenze)
        CaricaPlugin($nome,$dipendenze);
} 

Cosa fanno le due funzioni? la prima cerca di caricare tutti i plugin attivi. In realtà CaricaPlugin è capace di distinguere tra ciò che è già stato caricato e ciò che non lo è.

Se un plugin va caricato prima carica le dipendenze richiamando se stessa, così se una dipendenza ha ulteriori dipendenze anche vengono caricate prima della dipendenza e ciò ricorsivamente. La ricorsione si interrompe quando raggiungo i plugin senza dipendenze e dando il via alle require_once nell'ordine giusto.

Con buona pace per i plugin e per il topological sorting, dato che abbiamo i riferimenti in senso inverso, ovvero dalla foglia verso la radice (il core), non facciamo altro che ricostruire la sequenza dei caricamenti nello stack delle chiamate della funzione caricaplugin invertendo di fatto tale ordine, dalla radice (plugin senza dipendenze) verso le foglie, ogni folta che la funzione va a concludersi e prescindendo dal nodo (plugin) da cui avviamo l'operazione. I già caricati vengono ignorati.

Attento ai riferimenti ciclici che ti bruciano lo stack facendoti cadere in chiamate ricorsive infinite.

Spero di esser stato chiaro.

Avviamente non ho potuto testare il codice ma dovrebbe essere corretto.

[Agape]

ok...rieccomi
il tuo codice mi è servito molto per capire come agire ma aveva alcuni bug. Allora ho deciso di fare un merge tra i due. la soluzione definitiva e funzionante è questa:

$dependencies = array();

initialize_plugins();

function initialize_plugins() {
    global $db,$dependencies;
    
     $sql = "SELECT flatname, dependencies FROM plugins WHERE active='1'";
     foreach ($db->query($sql) as $row) {
         if (!is_array(json_decode($row['dependencies'])))
             $dependencies[$row['flatname']] = array();
         else
             $dependencies[$row['flatname']] = json_decode($row['dependencies']);
         
     }
    
    $order = array();
    
    foreach ($dependencies as $plugin => $foo) {
        $order [$plugin] = plugin_depth($plugin, $order);
    }
}

function plugin_depth($plugin, $order) {
    
    global $dependencies;
    
    $depths [0] = 0;
    
    foreach ($dependencies[$plugin] as $dependency) {
        if (array_key_exists($dependency, $order))
            $depths[] = $order[$dependency];
        else
            $depths[] = plugin_depth($dependency, $order);
    }
    
    
    sort($depths);
    
    return end($depths) + 1;
} 

ora basta caricare prima i plugin con 'depth' minore e il gioco è fatto! grazie!

[postato nel caso qualcuno avesse bisogno in futuro di un codice del genere ^^]

ciao!