Nouveau projet Open Source Invenietis

[Olivier Spinelli]

Bonjour,

Un petit mail pour vous annoncer la naissance de Yodii-Script : https://github.com/Invenietis/yodii-script
Une petite idée de ce que cela fait :
[Test]
public void closure_with_two_levels()
{
string s = @"
function next( s )
{
let _seed = s;
function oneMore() {
return function() { return ++_seed; };
}
return oneMore();
}
let f = next(0);
f(0) + f(0) + f(0);
f = next(0);
f(0) + f(0) + f(0) + f(0);
";
RuntimeObj o = ScriptEngine.Evaluate( s );
Assert.IsInstanceOf<JSEvalNumber>( o );
Assert.That( o.ToDouble(), Is.EqualTo( 1 + 2 + 3 + 4 ) );
}

Mais pourquoi viens-je de passer 9 jours en apnée pour réinventer une roue ?
Parce que cette roue, n’existe pas vraiment, en fait… Pour CiviKey nous voulions un langage de script simple et sûre avec quelques fonctionnalités d’IDE simple pour pouvoir débugger un peu (la cible est le « casual développer », pas le professionnel du développement).
Facile ? Microsoft.ScriptingEngine, IronPython, NLua, Clearscript, etc…
Des étudiants ont essayé (c’est leur projet de semestre). Plus facile à dire qu’à faire. En substance :

- On ne contrôle pas grand-chose de l’exécution

o Exécution synchrone et on prie… Pas de step by step possible, de breakpoint, de capacités de debuggage intégré.

o Peu ou pas de contrôle sur les capacités du script à faire des choses avec le monde extérieur (tiens un petit appel à fopen()…).

- Gros enjeu sur les performances pour ces gens-là. JIT etc. alors que nous, on s’en moque totalement.

- Déploiement en mode pure bonheur : il faut installer des trucs sur la machine… avec la joie des PATH et toutes ces joyeusetés.
Bref, cela ne convenait pas. J’ai donc repris CK-Javascript et l’ai transformé en petit langage simple fondée sur javascript (avec des différences assumées – let, pas de var entre autre). Mais, surtout, l’évaluation est totalement en machine à état.
Pas de threading, pas de problèmes d’interactions avec les éléments de GUI.
Un point important : l’évaluation des objets de contexte (typiquement les API externes que l’on souhaite injecter, mettre à disposition du script) se fait d’abord PAR les objets de contexte eux-mêmes (puis éventuellement par des visiteurs standard qui utiliseraient typiquement la System.Reflection). Cela permet de :

- Contrôler les accès aussi finement qu’on le souhaite à ce que l’on veut.

- De créer des « Modèles » totalement virtuels, sans POCO ou Proxys à écrire.

Les composants sont :

- Le tokenizer,

- L’Analyzer (façon Vaughan-Pratt ) qui produit un AST d’Expr (assez con) immuable.

- Un ExprVisitor de mutation générique sur son type de retour.

- Un EvalVisitor qui va exécuter l’AST.

- La machine à état est réalisée via des Frames qui capturent l’état de la pile d’exécution et des promesses/deferred plutôt marrants.

Certes, le côté machine à état a un coût. Mais on y gagne tellement en contrôle (et les performances devraient être amplement suffisantes pour nos besoins !). Afin de donner un aperçu de comment cela fonctionne, ci-dessous l’implémentation du « if » au travers des différentes couches :


- La classe de base de l’AST :

public abstract class Expr
{
protected Expr( SourceLocation location, bool isbreakable = false )
{
Location = location;
IsBreakable = isbreakable;
}

public readonly bool IsBreakable;

public readonly SourceLocation Location;

internal protected abstract T Accept<T>( IExprVisitor<T> visitor );
}


- Le « If » lui-même :

public class IfExpr : Expr
{
public IfExpr( SourceLocation location, bool isTernary, Expr condition, Expr whenTrue, Expr whenFalse )
: base( location, true )
{
IsTernaryOperator = isTernary;
Condition = condition;
WhenTrue = whenTrue;
WhenFalse = whenFalse;
}

/// <summary>
/// Gets whether this is a ternary ?: expression (<see cref="WhenFalse"/> necessarily exists).
/// Otherwise, it is an if statement: <see cref="WhenTrue"/> and WhenFalse are Blocks (and WhenFalse may be null).
/// </summary>
public bool IsTernaryOperator { get; private set; }

public Expr Condition { get; private set; }

public Expr WhenTrue { get; private set; }

public Expr WhenFalse { get; private set; }

[DebuggerStepThrough]
internal protected override T Accept<T>( IExprVisitor<T> visitor )
{
return visitor.Visit( this );
}

/// <summary>
/// This is just to ease dubugging...
/// </summary>
public override string ToString()
{
string s = "if(" + Condition.ToString() + ") then {" + WhenTrue.ToString() + "}";
if( WhenFalse != null ) s += " else {" + WhenFalse.ToString() + "}";
return s;
}
}


- Le bout de l’analyser qui le produit (je vous met le code complet, sauf la méthode Expression( int rightBindingPower ) qui est le cœur et un peu plus complexe ainsi que la gestion du scope des variables – pas simple).
C’est un peu long, mais cela permet de bien voir le rôle et le travail d’un Analyzer et comment on peut découper en petites méthodes des bouts de trucs réutilisables (par d’autres instructions) :

Expr HandleIf()
{
// "if" identifier has already been matched.
SourceLocation location = _parser.PrevNonCommentLocation;
Expr c;
if( !IsCondition( out c ) ) return c;
Expr whenTrue = HandleStatement();
Expr whenFalse = null;
if( _parser.MatchIdentifier( "else" ) ) whenFalse = HandleStatement();
return new IfExpr( location, false, c, whenTrue, whenFalse );
}

bool IsCondition( out Expr c )
{
if( !_parser.Match( JSTokeniserToken.OpenPar ) ) c = new SyntaxErrorExpr( _parser.Location, "Expected '('." );
else
{
c = Expression( 0 );
if( _parser.Match( JSTokeniserToken.ClosePar ) ) return true;
c = new SyntaxErrorExpr( _parser.Location, "Expected ')'." );
}
return false;
}

Expr HandleStatement()
{
if( _parser.Match( JSTokeniserToken.OpenCurly ) ) return HandleBlock();
return Expression( 0 );
}

Expr HandleBlock( Expr first = null )
{
if( first == null ) _scope.OpenScope();
List<Expr> statements = new List<Expr>();
if( first != null && first != NopExpr.Default ) statements.Add( first );
FillStatements( statements );
// Always close the scope (even opened by the caller).
return BlockFromStatements( statements, _scope.CloseScope() );
}

void FillStatements( List<Expr> statements )
{
while( !_parser.Match( JSTokeniserToken.CloseCurly ) && !_parser.IsEndOfInput )
{
Expr e = Expression( 0 );
_parser.Match( JSTokeniserToken.SemiColon );
if( e != NopExpr.Default ) statements.Add( e );
if( e is SyntaxErrorExpr ) break;
}
}

static Expr BlockFromStatements( List<Expr> statements, IReadOnlyList<AccessorDeclVarExpr> locals )
{
if( statements.Count == 0 ) return NopExpr.Default;
if( statements.Count == 1 && locals.Count == 0 ) return statements[0];
return new BlockExpr( statements.ToArray(), locals );
}


- Pour être complet, la méthode du visiteur de mutation pour le IfExpr :

public class ExprVisitor : IExprVisitor<Expr>
{
...
public virtual Expr Visit( IfExpr e )
{
Expr cV = VisitExpr( e.Condition );
Expr tV = VisitExpr( e.WhenTrue );
Expr fV = e.WhenFalse != null ? VisitExpr( e.WhenFalse ) : null;
return cV == e.Condition && tV == e.WhenTrue && fV == e.WhenFalse ? e : new IfExpr( e.Location, e.IsTernaryOperator, cV, tV, fV );
}
...
}


- Pour l’exécution, tout l’enjeu est de gérer la machine à état sans trop d’overhead pour le développeur…
La, base : l’exécution visite l’arbre et retourne à chaque fois des « promesses » de résultat. Un résultat résolu est un RuntimeObj (classe de base), Il y a des spécialisations pour les valeurs (JSEvalBoolean, JSEvalString, JSEvalNumber, etc. qui correspondent aux types de base du javascript), une spécialisation RefRuntimeObj (qui est une référence vers un RuntimeObj) et un objet un peu spécial : le RuntimeSignal qui se décline en deux spécialisations : le RuntimeError et le RuntimeFlowBreaking qui permet d’implémenter les break, continue et return (et dans pas longtemps, du coup, le try / catch en interceptant les erreurs ☺).

[cid:image0...@01D082A9.E0455B30]





- Une promesse de résultat est une petite struct toute bête avec deux champs et quelques petits helpers :


/// <summary>
/// Promise of an <see cref="Expr"/>: either a resolved <see cref="RuntimeObj"/> or a <see cref="IDeferredExpr"/>.
/// </summary>
public struct PExpr
{
public readonly IDeferredExpr Deferred;
public readonly RuntimeObj Result;

public PExpr( IDeferredExpr pending )
: this( pending, null )
{
}

public PExpr( RuntimeObj resultOrSignal )
: this( null, resultOrSignal )
{
}

PExpr( IDeferredExpr pending, RuntimeObj resultOrSignal )
{
Deferred = pending;
Result = resultOrSignal;
}

public bool IsUnknown { get { return Result == null && Deferred == null; } }

public bool IsSignal { get { return Result is RuntimeSignal; } }

public bool IsErrorResult { get { return Result is RuntimeError; } }

public bool IsPending { get { return Deferred != null; } }

public bool IsResolved { get { return Result != null; } }

public bool IsPendingOrSignal { get { return Deferred != null || IsSignal; } }

public bool IsValidResult { get { return Result != null && !IsSignal; } }

public override string ToString()
{
string sP = Deferred != null ? String.Format( "Deferred = {0}", Deferred.Expr ) : null;
string sR = Result != null ? String.Format( "Result = {0}", Result ) : null;
if( sP == null ) return sR != null ? sR : "(Unknown)";
if( sR == null ) return sP;
return sP + ", " + sR;
}
}



- Et son copain qui saura (si Result est null), produire (résoudre) le résultat :

public interface IDeferredExpr
{
/// <summary>
/// Gets the expression.
/// </summary>
Expr Expr { get; }

/// <summary>
/// Gets the resolved result. Null until this deffered is resolved.
/// </summary>
RuntimeObj Result { get; }

/// <summary>
/// Gets whether a result (or an error) has been resolved.
/// </summary>
bool IsResolved { get; }

/// <summary>
/// Executes the required code until this expression is resolved.
/// </summary>
/// <returns>A promise that may not be resolved if a breakpoint is met.</returns>
PExpr StepOver();

/// <summary>
/// Executes only one step.
/// </summary>
/// <returns>A promise that may be resolved if all the required code has been executed.</returns>
PExpr StepIn();
}


- Pour finir, et si vous vous êtes accroché jusque-là, l’évaluation du IfExpr lui-même, qui est une partie de l’EvalVisitor. Les petits helpers permettent d’avoir du code relativement lisible… la machine à état se cache

dans les petites struct PExpr : le Frame ne sera détruit que lorsqu’il aura produit un résultat. Si l’exécution est arrêtée au fin fond d’une fonction appellée par la Condition par exemple, la Frame reste active (sur la pile) et est prête à reprendre le cours de son travail pile où elle s’était arrêtée…

public partial class EvalVisitor
{
class IfExprFrame : Frame<IfExpr>
{
PExpr _condition;
PExpr _whenTrue;
PExpr _whenFalse;

public IfExprFrame( EvalVisitor evaluator, IfExpr e )
: base( evaluator, e )
{
}

protected override PExpr DoVisit()
{
if( IsPendingOrSignal( ref _condition, Expr.Condition ) ) return PendingOrSignal( _condition );

if( _condition.Result.ToBoolean() )
{
if( IsPendingOrSignal( ref _whenTrue, Expr.WhenTrue ) ) return PendingOrSignal( _whenTrue );
return SetResult( _whenTrue.Result );
}

if( Expr.WhenFalse != null )
{
if( IsPendingOrSignal( ref _whenFalse, Expr.WhenFalse ) ) return PendingOrSignal( _whenFalse );
return SetResult( _whenFalse.Result );
}
return SetResult( RuntimeObj.Undefined );
}
}

public PExpr Visit( IfExpr e )
{
return new IfExprFrame( this, e ).Visit();
}
}

Bon… voilà… Je ne dis pas que c’est trivial. Mais ce n’est pas non plus monstrueux. Bon, d’accord, il y a des choses plus complexes qui sous-tendent tout cela mais, au final, cela marche très bien et on n’a pas à s’en occuper.
Surtout si l’on utilise l’objet ScriptEngine :

public partial class ScriptEngine
{
/// <summary>
/// Initializes a new <see cref="ScriptEngine"/>, optionally bound to an existing <see cref="GlobalContext"/>.
/// </summary>
/// <param name="ctx">Optional global context to use.</param>
public ScriptEngine( GlobalContext ctx = null ) ...

/// <summary>
/// Gets the breakpoint manager that will be used.
/// </summary>
public BreakpointManager Breakpoints { ... }
}

/// <summary>
/// Gets the <see cref="GlobalContext"/>.
/// </summary>
public GlobalContext Context { ... }

/// <summary>
/// Executes a string by first calling <see cref="ExprAnalyser.AnalyseString"/>.
/// </summary>
/// <param name="s">The string to execute.</param>
/// <returns>A result that may be pending...</returns>
public Result Execute( string s ) ...

/// <summary>
/// Executes an already analysed script.
/// </summary>
/// <param name="s">The string to execute.</param>
/// <returns>A result that may be pending...</returns>
public Result Execute( Expr e ) ...
}

Et son copain le Result:

/// <summary>
/// Result of the <see cref="G:Execute"/> methods. Exposes a <see cref="Status"/> and an observable list of the stack.
/// Offers a simple <see cref="Continue"/> method whenever the Status is <see cref="ScriptEngineStatus.IsPending"/>.
/// </summary>
public class Result : IDisposable
{
/// <summary>
/// Gets the result of the execution. When stepping, this is the result of the top frame that has just been resolved.
/// </summary>
public RuntimeObj CurrentResult ...
/// <summary>
/// Gets the error that stopped the execution if any.
/// </summary>
public RuntimeError Error ...

/// <summary>
/// Gets the current engine status. When <see cref="ScriptEngineStatus.IsPending"/>, <see cref="Continue"/> can be called.
/// </summary>
public ScriptEngineStatus Status ...

/// <summary>
/// Continue the execution of the script. Must be called only when <see cref="Status"/> is <see cref="ScriptEngineStatus.IsPending"/> otherwise
/// an exception is thrown.
/// </summary>
public void Continue() ...

/// <summary>
/// Gets the raw frame stack as an observable list: the stack of all current <see cref="IDeferredExpr"/> beeing evaluated.
/// </summary>
/// <returns>An observable list that will be dynamically updated.</returns>
public IObservableReadOnlyList<IDeferredExpr> EnsureRawFrameStack() ...

/// <summary>
/// Resets the current execution. This frees the <see cref="ScriptEngine"/>: new calls to its <see cref="G: ScriptEngine.Execute"/ > can be made.
/// </summary>
public void Dispose() ...
}
}

Voilà, là, ce mail est vraiment terminé. Même si j’aurai des tas d’autres trucs à dire (par exemple que je suis très fier de la gestion des scopes statiques et dynamiques en O(1) et de l’implémentation en 3 heures de la closure ☺).
Ah ! J’oubliais… La dll compilé en release .Net 4.5 pèse aujourd’hui 73KB et n’a de dépendances qu’à CK.Core (mais je vais essayer de la supprimer). Bien sûr, il faut rajouter des choses, mais pas non plus tant que ça a priori…

Le code est dispo sur GitHub. Si d’aventure vous connaissez quelqu’un qui souhaite mettre du script simple et safe dans une application nous serions ravi d’en discuter avec lui ☺.

Spi