mcs/class/Microsoft.JScript/Microsoft.JScript/IdentificationTable.cs

   1 //
   2 // IdentificationTable.cs: Implementation of environments for jscript. Using a
   3 // modified version of the algorithm and date structure presented by
   4 // Andrew W. Appel in his book Modern compiler implementation in Java,
   5 // second edition.
   6 //
   7 // Author:
   8 //      Cesar Lopez Nataren (cnataren@novell.com)
   9 //
  10 // (C) 2003, Cesar Lopez Nataren
  11 // Copyright (C) 2005 Novell Inc (http://novell.com)
  12 //
  13
  14 //
  15 // Permission is hereby granted, free of charge, to any person obtaining
  16 // a copy of this software and associated documentation files (the
  17 // "Software"), to deal in the Software without restriction, including
  18 // without limitation the rights to use, copy, modify, merge, publish,
  19 // distribute, sublicense, and/or sell copies of the Software, and to
  20 // permit persons to whom the Software is furnished to do so, subject to
  21 // the following conditions:
  22 //
  23 // The above copyright notice and this permission notice shall be
  24 // included in all copies or substantial portions of the Software.
  25 //
  26 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  27 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  28 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  29 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  30 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  31 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  32 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  33 //
  34
  35 using System;
  36 using System.Reflection;
  37 using System.Collections;
  38
  39 namespace Microsoft.JScript {
  40         /// <summary>
  41         /// Class that encapsulates a string id for faster hashing purposes.
  42         /// </summary>
  43         internal class Symbol {
  44                 private string name;
  45                 private static Hashtable dict = new Hashtable ();
  46
  47                 internal string Value {
  48                         get { return name; }
  49                 }
  50
  51                 private Symbol (string name)
  52                 {
  53                         this.name = name;
  54                 }
  55
  56                 public override string ToString ()
  57                 {
  58                         return name;
  59                 }
  60
  61                 /// <summary>
  62                 /// Return the unique symbol associated with a
  63                 /// string. Repeated calls to CreateSymbol will return the
  64                 /// same Symbol.
  65                 /// </summary>
  66                 internal static Symbol CreateSymbol (string n)
  67                 {
  68                         n = LateBinding.MapToInternalName (n);
  69                         string u = String.Intern (n);
  70                         Symbol s = (Symbol) dict [u];
  71
  72                         if (s == null) {
  73                                 s = new Symbol (u);
  74                                 dict [u] = s;
  75                         }
  76                         return s;
  77                 }
  78         }
  79
  80         /// <summary>
  81         /// Associates a symbol to its declaring object.
  82         /// </summary>
  83         internal class Binder {
  84                 object value;
  85                 Symbol prev_top;
  86
  87                 /// <remarks>
  88                 /// If the symbol is already in the environment, resolves
  89                 /// collisions with external chaining.
  90                 /// </remarks>
  91                 Binder tail;
  92
  93                 internal object Value {
  94                         get { return value; }
  95                         set { this.value = value; }
  96                 }
  97
  98                 internal Binder Tail {
  99                         get { return tail; }
 100                 }
 101
 102                 internal Symbol PrevTop {
 103                         get { return prev_top; }
 104                 }
 105
 106                 internal Binder (object value, Symbol prev_top, Binder tail)
 107                 {
 108                         this.value = value;
 109                         this.prev_top = prev_top;
 110                         this.tail = tail;
 111                 }
 112         }
 113
 114         /// <summary>
 115         /// Environment implementation, each key must be a Symbol and we take
 116         /// care of scoping.
 117         /// </summary>
 118         internal class IdentificationTable {
 119                 private Hashtable dict = new Hashtable ();
 120                 private Symbol top;
 121                 private Binder marks;
 122                 private Stack locals;
 123                 private bool previous_scope = false;
 124                 private bool catch_scope = false;
 125                 internal bool CatchScope {
 126                         get { return catch_scope; }
 127                 }
 128
 129                 internal int depth;
 130
 131                 internal IdentificationTable ()
 132                 {
 133                         locals = new Stack ();
 134                         locals.Push (new Hashtable ());
 135                         depth = 0;
 136                 }
 137
 138                 internal bool Contains (Symbol key)
 139                 {
 140                         Binder e = (Binder) dict [key];
 141                         return e != null;
 142                 }
 143
 144                 /// <summary>
 145                 /// Gets the object associated to the symbol in the table
 146                 /// </summary>
 147                 internal object Get (Symbol key)
 148                 {
 149                         Binder e = (Binder) dict [key];
 150
 151                         if (e == null)
 152                                 return null;
 153                         else
 154                                 return e.Value;
 155                 }
 156
 157                 /// <summary>
 158                 /// Bind a key
 159                 /// </summary>
 160                 internal void Enter (Symbol key, object value)
 161                 {
 162                         Binder e = (Binder) dict [key];
 163
 164                         /// <remarks>
 165                         /// If a Binder's Value is null means that it
 166                         /// represents a in-transit binding, we must
 167                         /// set its value to something useful.
 168                         /// </remarks>
 169                         if (e != null && e.Value == null)
 170                                 e.Value = value;
 171                         else {
 172                                 //
 173                                 // If 'key' is already on the table we form a
 174                                 // Binder's chain, otherwise we include the new key
 175                                 // represented with its association object.
 176                                 //
 177                                 dict [key] = new Binder (value, top, (Binder) dict [key]);
 178
 179                                 //
 180                                 // make 'key' the most recent symbol bound
 181                                 //
 182                                 top = key;
 183                         }
 184                         Hashtable top_ht = (Hashtable) locals.Peek ();
 185                         string val = key.Value;
 186                         top_ht[val] = value;
 187                 }
 188
 189                 /// <summary>
 190                 /// Delete symbol from the table
 191                 /// </summary>
 192                 internal void Remove (Symbol key)
 193                 {
 194                         Binder e = (Binder) dict [key];
 195                         if (e != null)
 196                                 if (e.Tail != null)
 197                                         dict [key] = e.Tail;
 198                                 else
 199                                         dict.Remove (key);
 200                 }
 201
 202                 internal void BeginScope ()
 203                 {
 204                         BeginScope (false);
 205                 }
 206
 207                 /// <summary>
 208                 /// Remembers the current state of the table
 209                 /// </summary>
 210                 internal void BeginScope (bool catchScope)
 211                 {
 212                         previous_scope = catch_scope;
 213                         catch_scope = catchScope;
 214
 215                         marks = new Binder (null, top, marks);
 216                         top = null;
 217
 218                         locals.Push (new Hashtable ());
 219                         depth++;
 220                 }
 221
 222                 /// <summary>
 223                 /// Restores the table to what it was at the most recent BeginScope
 224                 /// that has not already been ended
 225                 /// </summary>
 226                 internal void EndScope ()
 227                 {
 228                         //
 229                         // Delete all the elements until we find
 230                         // that top is null, that occurs when we find
 231                         // the scope marker.
 232                         //
 233                         while (top != null) {
 234                                 Binder e = (Binder) dict [top];
 235
 236                                 //
 237                                 // If there's a chain we delete the first
 238                                 // element of it, otherwise remove the symbol
 239                                 // from the table.
 240                                 //
 241                                 if (e.Tail != null)
 242                                         dict [top] = e.Tail;
 243                                 else
 244                                         dict.Remove (top);
 245
 246                                 top = e.PrevTop;
 247                         }
 248
 249                         //
 250                         // marks.PrevTop always contains the latest symbol
 251                         // which was bound before the new scope was created.
 252                         //
 253                         top = marks.PrevTop;
 254
 255                         //
 256                         // delete the latest scope mark
 257                         //
 258                         marks = marks.Tail;
 259                         locals.Pop ();
 260
 261                         depth--;
 262                         catch_scope = previous_scope;
 263                 }
 264
 265                 internal object [] CurrentLocals {
 266                         get {
 267                                 Stack stack = new Stack ();
 268                                 Symbol _top = top;
 269
 270                                 while (_top != null) {
 271                                         Binder e = (Binder) dict [_top];
 272                                         stack.Push (e.Value);
 273                                         _top = e.PrevTop;
 274                                 }
 275                                 if (stack.Count == 0)
 276                                         return null;
 277
 278                                 object [] res = new object [stack.Count];
 279                                 stack.CopyTo (res, 0);
 280                                 return res;
 281                         }
 282                 }
 283
 284                 internal bool InCurrentScope (Symbol id)
 285                 {
 286                         Hashtable hash = (Hashtable) locals.Peek ();
 287                         return hash.ContainsKey (id.Value) && hash [id.Value] != null;
 288                 }
 289
 290                 internal void AddToCurrentLocals (string name, object o)
 291                 {
 292                         ((Hashtable) locals.Peek ()).Add (name, o);
 293                 }
 294
 295                 internal DictionaryEntry [] LocalsAtDepth (int depth)
 296                 {
 297                         object [] hashes = new object [locals.Count];
 298                         locals.CopyTo (hashes, 0);
 299                         Hashtable hash = (Hashtable) hashes [locals.Count - depth - 1];
 300                         DictionaryEntry [] _locals = new DictionaryEntry [hash.Count];
 301                         hash.CopyTo (_locals, 0);
 302                         return _locals;
 303                 }
 304         }
 305
 306
 307         //
 308         // Lookup table with namespace context.
 309         //
 310         internal class Environment {
 311
 312                 private Hashtable namespaces;
 313
 314                 internal Environment ()
 315                 {
 316                         namespaces = new Hashtable ();
 317
 318                         //
 319                         // global variables identification table
 320                         //
 321                         namespaces.Add (String.Empty, new IdentificationTable ());
 322                 }
 323
 324                 internal Environment (ScriptBlock [] blocks)
 325                         : this ()
 326                 {
 327                         //
 328                         // FIXME: when we implement the package stm. For each package
 329                         // name we must add a identification table that will store
 330                         // id's defined inside it.
 331                         //
 332
 333                         //
 334                         // integrate the builtin functions, objects, ...
 335                         //
 336                         BuildGlobalEnv ();
 337                 }
 338
 339                 //
 340                 // retrieves the identification table for the ns namespace
 341                 //
 342                 internal IdentificationTable GetIdentificationTable (string ns)
 343                 {
 344                         return (IdentificationTable) namespaces [ns];
 345                 }
 346
 347                 internal bool Contains (string ns, Symbol key)
 348                 {
 349                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 350
 351                         if (symbols == null)
 352                                 return false;
 353
 354                         return symbols.Contains (key);
 355                 }
 356
 357                 internal object Get (string ns, Symbol key)
 358                 {
 359                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 360
 361                         if (symbols == null)
 362                                 return null;
 363
 364                         return symbols.Get (key);
 365                 }
 366
 367                 internal void Enter (string ns, Symbol key, object value)
 368                 {
 369                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 370
 371                         if (symbols == null)
 372                                 throw new Exception (ns + " does not exist");
 373
 374                         symbols.Enter (key, value);
 375                 }
 376
 377                 internal void Remove (string ns, Symbol key)
 378                 {
 379                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 380
 381                         if (symbols == null)
 382                                 throw new Exception (ns + " does not exist");
 383
 384                         symbols.Remove (key);
 385                 }
 386
 387                 internal void BeginScope (string ns)
 388                 {
 389                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 390
 391                         if (symbols == null)
 392                                 throw new Exception (ns + " does not exist");
 393
 394                         symbols.BeginScope ();
 395                 }
 396
 397                 internal void BeginScope (string ns, bool catchScope)
 398                 {
 399                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 400
 401                         if (symbols == null)
 402                                 throw new Exception (ns + " does not exist");
 403
 404                         symbols.BeginScope (catchScope);
 405                 }
 406
 407                 internal void EndScope (string ns)
 408                 {
 409                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 410
 411                         if (symbols == null)
 412                                 throw new Exception (ns + " does not exist");
 413
 414                         symbols.EndScope ();
 415                 }
 416
 417                 internal object [] CurrentLocals (string ns)
 418                 {
 419                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 420
 421                         if (symbols == null)
 422                                 throw new Exception (ns + " does not exist");
 423
 424                         return symbols.CurrentLocals;
 425                 }
 426
 427                 internal int Depth (string ns)
 428                 {
 429                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 430
 431                         if (symbols == null)
 432                                 throw new Exception (ns + " does not exist");
 433
 434                         return symbols.depth;
 435                 }
 436
 437                 internal bool InCurrentScope (string ns, Symbol id)
 438                 {
 439                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 440
 441                         if (symbols == null)
 442                                 throw new Exception (ns + " does not exist");
 443
 444                         return symbols.InCurrentScope (id);
 445                 }
 446
 447                 internal bool CatchScope (string ns)
 448                 {
 449                         IdentificationTable symbols = (IdentificationTable) namespaces [ns];
 450
 451                         if (symbols == null)
 452                                 throw new Exception (ns + " does not exist");
 453
 454                         return symbols.CatchScope;
 455                 }
 456
 457                 internal void BuildGlobalEnv ()
 458                 {
 459                         //
 460                         // built in print function
 461                         //
 462                         if (SemanticAnalyser.print)
 463                                 Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("print"), new BuiltIn ("print", false, true));
 464
 465                         /* value properties of the Global Object */
 466                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("NaN"), new BuiltIn ("NaN", false, false));
 467                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Infinity"), new BuiltIn ("Infinity", false, false));
 468                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("undefined"), new BuiltIn ("undefined", false, false));
 469                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("null"), new BuiltIn ("null", false, false));
 470
 471                         /* function properties of the Global Object */
 472                         object [] custom_attrs;
 473                         Type global_object = typeof (GlobalObject);
 474                         MethodInfo [] methods = global_object.GetMethods (BindingFlags.Public | BindingFlags.Static | BindingFlags.DeclaredOnly);
 475                         foreach (MethodInfo mi in methods) {
 476                                 custom_attrs = mi.GetCustomAttributes (typeof (JSFunctionAttribute), false);
 477                                 foreach (JSFunctionAttribute attr in custom_attrs)
 478                                         if (attr.IsBuiltIn)
 479                                                 Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol (mi.Name), new BuiltIn (SemanticAnalyser.ImplementationName (attr.BuiltIn.ToString ()), false, true));
 480                         }
 481
 482                         /* built in objects */
 483                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Object"), new BuiltIn ("Object", true, true));
 484                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Function"), new BuiltIn ("Function", true, true));
 485                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Array"), new BuiltIn ("Array", true, true));
 486                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("String"), new BuiltIn ("String", true, true));
 487                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Boolean"), new BuiltIn ("Boolean", true, true));
 488                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Number"), new BuiltIn ("Number", true, true));
 489                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Math"), new BuiltIn ("Math", false, false));
 490                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Date"), new BuiltIn ("Date", true, true));
 491                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("RegExp"), new BuiltIn ("RegExp", true, true));
 492
 493                         /* built in Error objects */
 494                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("Error"), new BuiltIn ("Error", true, true));
 495                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("EvalError"), new BuiltIn ("EvalError", true, true));
 496                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("RangeError"), new BuiltIn ("RangeError", true, true));
 497                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("ReferenceError"), new BuiltIn ("ReferenceError", true, true));
 498                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("SyntaxError"), new BuiltIn ("SyntaxError", true, true));
 499                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("TypeError"), new BuiltIn ("TypeError", true, true));
 500                         Enter (SemanticAnalyser.GlobalNamespace, Symbol.CreateSymbol ("URIError"), new BuiltIn ("URIError", true, true));
 501                 }
 502         }
 503 }