vm.js (13591B)
1 function init() { 2 window.setTimeout("log('Start'); window.setTimeout('test_vm_call_and_compile()', 0);", 100); 3 } 4 5 /* **************************************** */ 6 7 Array.prototype.append = function(array2) { 8 for (i = 0; i < array2.length; i++) { 9 this[this.length] = array2[i]; 10 } 11 }; 12 13 Array.prototype.peek = function(n) { 14 return this[this.length-1-n]; 15 }; 16 17 Array.prototype.triTopologique = function() { 18 tri = []; 19 dejavu = this.map(function(deps, n) {return false;}); 20 profondeur = function(deps, n) { 21 dejavu[n] = true; 22 deps.each(function(v) { 23 if (!dejavu[v]) { 24 profondeur(this[v], v); 25 } 26 }.bind(this)); 27 tri.push(n); 28 }.bind(this); 29 this.each(function(deps, n){ 30 if (!dejavu[n]) { 31 profondeur(deps, n); 32 } 33 }); 34 return tri; 35 }; 36 37 /* */ 38 39 function log(str) { 40 $('log').insert("<div>" + str + "</div>"); 41 } 42 43 function trace(str) { 44 if (typeof console != "undefined") { 45 console.log(str); 46 } 47 } 48 49 function error(str) { 50 $('log').insert("<div class=\"error\">" + str + "</div>"); 51 _error(); 52 } 53 54 /* **************************************** */ 55 function vm() { 56 /* The stack (grows up) : 57 * 58 * top 59 * 60 * return value 61 * return value 62 * junk 63 * junk 64 * junk 65 * return address 66 * param 67 * param 68 * 69 * bottom 70 */ 71 72 this.clean = function() { 73 this.stack = $A(); // Stack 74 this.ip = 0; // Instruction pointer. 75 this.exit = false; // Halt 76 }; 77 this.eval = function(instructions) { 78 for (this.ip = 0; (!this.exit); this.ip++) { 79 var instr = instructions[this.ip]; 80 var op = this.operations[instr.operation]; 81 var args = instr.arguments; 82 trace(this.ip + " : [" + this.stack.join(",") + "] (" + instr.display() + ")"); 83 op.eval.apply(this, args); 84 } 85 return this.stack; 86 }; 87 88 // Initialize to a clean state. 89 this.clean(); 90 91 vm = this; 92 // I can't manage to create a constructor from witin vm's constuctor. So I use an anonymous object in place. 93 this.op = function() { 94 this.operation = arguments[0]; 95 this.arguments = []; 96 97 for (i = 1; i < arguments.length; i++) { 98 this.arguments.push(arguments[i]); 99 } 100 101 this.display = function() { 102 return vm.operations[this.operation].display.apply(this, this.arguments); 103 } 104 }; 105 106 this.operations = { 107 comment: { 108 display : function(text) { return "# " + text; }, 109 eval : function(text) {} 110 }, 111 lineskip: { 112 display : function() { return ""; }, 113 eval : function() {} 114 }, 115 pop: { 116 display : function() { return "pop"; }, 117 eval : function() { this.stack.pop(); } 118 }, 119 push: { 120 display : function(val) { return "push " + val; }, 121 eval : function(val) { this.stack.push(val); } 122 }, 123 // Aller chercher un élément plus bas dans la pile 124 peek: { 125 display : function(shift) { return "peek " + shift; }, 126 eval : function(shift) { this.stack.push(this.stack.peek(shift)); } 127 }, 128 // Remplacer un élément plus bas dans la pile (contraire de peek) 129 // "peek 10; poke 10" est équivalent à ne rien faire du tout. 130 poke: { 131 display : function(shift) { return "poke " + shift; }, 132 eval : function(shift) { 133 e = this.stack.pop(); 134 this.stack[this.stack.length - 1 - shift] = e; 135 } 136 }, 137 // somme des 2 éléments en haut de la pile 138 add: { 139 display : function() { return "add"; }, 140 eval : function() { 141 a = this.stack.pop(); 142 b = this.stack.pop(); 143 this.stack.push(a + b); 144 } 145 }, 146 // Saut inconditionnel vers une instruction 147 jump: { 148 display : function(instr) { return "jump " + instr; }, 149 eval : function(instr) { this.ip = instr - 1; } 150 }, 151 // N'exécute pas l'instruction suivante ssi le sommet de la pile vaut 0 (Skip if Zero) 152 sz: { 153 display : function() { return "sz"; }, 154 eval : function() { if (this.stack.peek(0) == 0) { this.ip++; } } 155 }, 156 // Appeller la fonction instr, avec nbparam paramètres. 157 call: { 158 display : function(instr, nbparam) { return "call " + instr; }, 159 eval : function(instr, nbparam) { 160 this.stack.push(this.ip); 161 this.ip = instr - 1; 162 } 163 }, 164 ret: { 165 display : function() { return "return"; }, 166 eval : function() { this.ip = this.stack.pop(); } 167 }, 168 exit: { 169 display : function() { return "exit"; }, 170 eval : function() { this.exit = true; } 171 } 172 }; 173 }; 174 175 function world(name) { 176 this.blocs = []; 177 this.newBloc = function(name, nbEntrees, nbSorties) { 178 uid = this.blocs.length; 179 this.blocs[uid] = new bloc(uid, name, nbEntrees, nbSorties); 180 return this.blocs[uid]; 181 } 182 this.compile = function(vm, entryPoint) { 183 var comp = []; 184 var pos = []; 185 var curpos = 0; 186 var comp = []; 187 188 comp.push(new vm.op("comment", "Point d'entrée du programme :")); 189 comp.push(new vm.op("lineskip")); 190 comp.push(new vm.op("call", entryPoint.uid)); 191 comp.push(new vm.op("exit")); 192 curpos += 4; 193 194 this.blocs.each(function (b) { 195 bc = b.compile(vm); 196 197 comp.push(new vm.op("lineskip")); 198 curpos++; 199 200 pos[b.uid] = curpos; 201 comp.append(bc); 202 curpos += bc.length; 203 }); 204 205 for (instr = 0; instr < comp.length; instr++) { 206 if (comp[instr].operation == "call") { 207 comp[instr] = new vm.op("call", pos[comp[instr].arguments[0]]); 208 } 209 } 210 211 comp.display = function () { 212 return this.map(function (e, i) { return i + "> " + e.display(); }).join("\n") + "</pre></code>" 213 } 214 215 return comp; 216 } 217 } 218 219 function bloc(uid, name, nbEntrees, nbSorties) { 220 this.uid = uid; 221 this.name = name; 222 this.nbEntrees = nbEntrees; 223 this.nbSorties = nbSorties; 224 this.blocs = new Array(); 225 this.blocdeps = new Array(); 226 this.portdeps = new Array(); 227 this.addBloc = function(bloc) { 228 this.blocs.push(bloc); 229 this.blocdeps.push($A()); 230 this.portdeps.push($A()); // TODO : détecter quand il n'y a pas le bon nombre de connexions... 231 return this.blocs.length - 1; 232 }; 233 this.connect = function(blocSortie, portSortie, blocEntree, portEntree) { 234 this.portdeps[blocEntree][portEntree] = { 235 blocSortie: blocSortie, 236 portSortie: portSortie, 237 }; 238 this.blocdeps[blocEntree].push(blocSortie); 239 }; 240 this.innerCompile = function(vm) { 241 var tri = this.blocdeps.triTopologique(); 242 243 // Est-ce vraiment nécessaire ? 244 // if (tri[0] != 0) { error("Les entrées ne sont pas en premier dans le bloc " + this.name); } 245 246 /* Stack : 247 * a return adress 248 * 9 resutl 1 of this bloc 249 * 8 result 0 of this bloc stackpos[1] = 8 250 * 7 result 0 of bloc 3 stackpos[3] = 7 251 * 6 result 2 of bloc 2 252 * 5 result 1 of bloc 2 253 * 4 result 0 of bloc 2 stackpos[2] = 4 254 * 3 return adress 255 * 2 param 2 256 * 1 param 1 257 * 0 param 0 stackpos[0] = 0 258 * 259 * Before ret, poke elements 7,9,a down to 260 * positions 0,1,2, and pop the rest. 261 */ 262 263 var stackpos = []; // Position dans la pile des résultats de chaque bloc. 264 stackpos[0] = this.nbEntrees; // paramètres + adresse de retour. 265 var curpos = this.nbEntrees; // Position actuelle du sommet de pile. Les paramètres ont déjà été mis sur la pile. 266 var comp = []; // «Bytecode» généré. 267 268 // 1 (les sorties) devrait être à la fin, potentiellement suivi par du code mort : 269 // des blocs non connectés à la sortie. On s'assure qu'il est bien à la fin. 270 // De plus, on enlève 0 (les entrées) car ils sont déjà sur la pile 271 tri = tri.without(0, 1); 272 tri.push(1); 273 274 tri.each(function (n) { 275 stackpos[n] = curpos; 276 var b = this.blocs[n]; 277 278 // On empile chaque paramètre du bloc à appeler. 279 for (var entree = 0; entree < b.nbEntrees; entree++) { 280 var dep = this.portdeps[n][entree]; 281 if (typeof dep == "undefined") { 282 error("Entrée " + entree + " manquante pour le bloc " + n + " (" + b.name + ") de " + this.name); 283 } 284 var pos = stackpos[dep.blocSortie] + dep.portSortie; 285 comp.push(new vm.op("peek", curpos - pos - 1)); 286 curpos++; 287 } 288 289 if (n != 1) { // Le bloc "sortie" est un fake 290 comp.push(new vm.op("call", b.uid)); // pusher l'adresse de retour et appeler le bloc 291 } 292 293 curpos -= b.nbEntrees; // le bloc appelé a empilé tous ses paramètres 294 curpos += b.nbSorties; // et a dépilé ses résultats 295 }, this); 296 297 return { code: comp, junk: curpos - this.nbSorties + 1 }; 298 }; 299 this.compile = function(vm) { 300 var comp = []; 301 302 comp.push(new vm.op("comment", "Bloc " + this.uid + " (" + this.name + ")")); 303 comp.push(new vm.op("lineskip")); 304 305 // On réserve la place pour écrire les valeurs de retour. 306 for (var i = 0; i < this.nbSorties - this.nbEntrees; i++) { 307 comp.push(new vm.op("push", "0")); 308 } 309 310 startpos = Math.max(this.nbEntrees, this.nbSorties); 311 312 // On récupère les entrées en les faisant «sauter par-dessus» l'adresse 313 // de retour et les places réservées pour la sortie (s'il y en a). 314 for (var i = 0; i < this.nbEntrees; i++) { 315 comp.push(new vm.op("peek", startpos)); 316 } 317 318 // Le code du bloc à proprement parler. 319 var inner = this.innerCompile(vm) 320 comp.append(inner.code); 321 322 // On fait remonter l'adresse de retour au-dessus des valeurs de retour. 323 comp.push(new vm.op("peek", startpos + inner.junk + this.nbSorties - this.nbEntrees)); 324 325 // On fait descendre les valeurs de retour et l'adresse de retour. 326 for (var i = 0; i < this.nbSorties + 1; i++) { 327 comp.push(new vm.op("poke", startpos + inner.junk)); 328 } 329 330 // On pop les calculs intermédiaires et (si nécessaire) les valeurs 331 // d'entrées qui n'ont pas été écrasées par une valeur de sortie. 332 for (var i = 0; i < (startpos + inner.junk) - this.nbSorties; i++) { 333 comp.push(new vm.op("pop")); 334 } 335 336 // Et ne pas oublier de faire return... 337 comp.push(new vm.op("ret")); 338 339 return comp; 340 } 341 342 // This is a hack... 343 this.addBloc({ // 0 : self inputs 344 name: "Entrées", 345 nbEntrees: 0, 346 nbSorties: this.nbEntrees, 347 compile: function(){ return []; } 348 }); 349 this.addBloc({ // 1 : self outputs 350 name: "Sorties", 351 nbEntrees: this.nbSorties, 352 nbSorties: 0, 353 compile: function(){ return []; } 354 }); 355 } 356 357 function test_vm_call_and_compile() { 358 w = new world("Brave"); 359 wPlus = w.newBloc("+", 2, 1); 360 wOne = w.newBloc("1", 0, 1); 361 wTwo = w.newBloc("2", 0, 1); 362 wThesum = w.newBloc("Une somme", 2, 1); 363 wTest = w.newBloc("Test", 0, 1); 364 365 wOne.innerCompile = function(vm) { return { junk: 0, code: [ new vm.op("push", 1) ] }; }; 366 wTwo.innerCompile = function(vm) { return { junk: 0, code: [ new vm.op("push", 2) ] }; }; 367 wPlus.innerCompile = function(vm) { return { junk: 0, code: [ new vm.op("add") ] }; }; 368 369 wiPlus1 = wThesum.addBloc(wPlus); 370 wiPlus2 = wThesum.addBloc(wPlus); 371 wiPlus3 = wThesum.addBloc(wPlus); 372 wiPlus4 = wThesum.addBloc(wPlus); 373 wiOne = wThesum.addBloc(wOne); 374 wiTwo = wThesum.addBloc(wTwo); 375 376 wThesum.connect(wiOne, 0, wiPlus1, 0); 377 wThesum.connect(wiTwo, 0, wiPlus1, 1); 378 wThesum.connect(wiPlus4, 0, 1, 0); 379 wThesum.connect(wiPlus1, 0, wiPlus2, 0); 380 wThesum.connect(wiTwo, 0, wiPlus2, 1); 381 wThesum.connect(0, 0, wiPlus3, 0); 382 wThesum.connect(0, 1, wiPlus3, 1); 383 wThesum.connect(wiPlus2, 0, wiPlus4, 0); 384 wThesum.connect(wiPlus3, 0, wiPlus4, 1); 385 386 wiThesum = wTest.addBloc(wThesum); 387 wiTest1 = wTest.addBloc(wOne); 388 wiTest2 = wTest.addBloc(wTwo); 389 wTest.connect(wiTest1, 0, wiThesum, 0); 390 wTest.connect(wiTest2, 0, wiThesum, 1); 391 wTest.connect(wiThesum, 0, 1, 0); 392 393 var testVM = new vm(); 394 compThesum = w.compile(vm, wTest); 395 396 log("<code><pre>" + compThesum.display()); 397 log(testVM.eval(compThesum).join(", ")); 398 399 /* var testVm = new vm(); 400 log(testVm.eval(compThesum).join(", ")); 401 402 testdisplay();*/ 403 }