JavaScriptCore/kjs/lookup.h

   1 // -*- c-basic-offset: 2 -*-
   2 /*
   3  *  This file is part of the KDE libraries
   4  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   5  *  Copyright (C) 2003 Apple Computer, Inc.
   6  *
   7  *  This library is free software; you can redistribute it and/or
   8  *  modify it under the terms of the GNU Lesser General Public
   9  *  License as published by the Free Software Foundation; either
  10  *  version 2 of the License, or (at your option) any later version.
  11  *
  12  *  This library is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  *  Lesser General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public
  18  *  License along with this library; if not, write to the Free Software
  19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21  */
  22
  23 #ifndef _KJSLOOKUP_H_
  24 #define _KJSLOOKUP_H_
  25
  26 #include "interpreter.h"
  27 #include "identifier.h"
  28 #include "object.h"
  29 #include <stdio.h>
  30
  31 namespace KJS {
  32
  33   /**
  34    * An entry in a hash table.
  35    */
  36   struct HashEntry {
  37     /**
  38      * s is the key (e.g. a property name)
  39      */
  40     const char *s;
  41     /**
  42      * value is the result value (usually an enum value)
  43      */
  44     int value;
  45     /**
  46      * attr is a set for flags (e.g. the property flags, see object.h)
  47      */
  48     short int attr;
  49     /**
  50      * params is another number. For property hashtables, it is used to
  51      * denote the number of argument of the function
  52      */
  53     short int params;
  54     /**
  55      * next is the pointer to the next entry for the same hash value
  56      */
  57     const HashEntry *next;
  58   };
  59
  60   /**
  61    * A hash table
  62    * Usually the hashtable is generated by the create_hash_table script, from a .table file.
  63    *
  64    * The implementation uses an array of entries, "size" is the total size of that array.
  65    * The entries between 0 and hashSize-1 are the entry points
  66    * for each hash value, and the entries between hashSize and size-1
  67    * are the overflow entries for the hash values that need one.
  68    * The "next" pointer of the entry links entry points to overflow entries,
  69    * and links overflow entries between them.
  70    */
  71   struct HashTable {
  72     /**
  73      * type is a version number. Currently always 2
  74      */
  75     int type;
  76     /**
  77      * size is the total number of entries in the hashtable, including the null entries,
  78      * i.e. the size of the "entries" array.
  79      * Used to iterate over all entries in the table
  80      */
  81     int size;
  82     /**
  83      * pointer to the array of entries
  84      * Mind that some entries in the array are null (0,0,0,0).
  85      */
  86     const HashEntry *entries;
  87     /**
  88      * the maximum value for the hash. Always smaller than size.
  89      */
  90     int hashSize;
  91   };
  92
  93   /**
  94    * @short Fast keyword lookup.
  95    */
  96   class Lookup {
  97   public:
  98     /**
  99      * Find an entry in the table, and return its value (i.e. the value field of HashEntry)
 100      */
 101     static int find(const struct HashTable *table, const Identifier &s);
 102     static int find(const struct HashTable *table,
 103                     const UChar *c, unsigned int len);
 104
 105     /**
 106      * Find an entry in the table, and return the entry
 107      * This variant gives access to the other attributes of the entry,
 108      * especially the attr field.
 109      */
 110     static const HashEntry* findEntry(const struct HashTable *table,
 111                                       const Identifier &s);
 112     static const HashEntry* findEntry(const struct HashTable *table,
 113                                       const UChar *c, unsigned int len);
 114
 115     /**
 116      * Calculate the hash value for a given key
 117      */
 118     static unsigned int hash(const Identifier &key);
 119     static unsigned int hash(const UChar *c, unsigned int len);
 120     static unsigned int hash(const char *s);
 121   };
 122
 123   class ExecState;
 124   class UString;
 125   /**
 126    * @internal
 127    * Helper for lookupFunction and lookupValueOrFunction
 128    */
 129   template <class FuncImp>
 130   inline Value lookupOrCreateFunction(ExecState *exec, const Identifier &propertyName,
 131                                       const ObjectImp *thisObj, int token, int params, int attr)
 132   {
 133       // Look for cached value in dynamic map of properties (in ObjectImp)
 134       ValueImp * cachedVal = thisObj->ObjectImp::getDirect(propertyName);
 135       /*if (cachedVal)
 136         fprintf(stderr, "lookupOrCreateFunction: Function -> looked up in ObjectImp, found type=%d\n", cachedVal->type());*/
 137       if (cachedVal)
 138         return Value(cachedVal);
 139
 140       Value val = Value(new FuncImp(exec,token, params));
 141       ObjectImp *thatObj = const_cast<ObjectImp *>(thisObj);
 142       thatObj->ObjectImp::put(exec, propertyName, val, attr);
 143       return val;
 144   }
 145
 146   /**
 147    * Helper method for property lookups
 148    *
 149    * This method does it all (looking in the hashtable, checking for function
 150    * overrides, creating the function or retrieving from cache, calling
 151    * getValueProperty in case of a non-function property, forwarding to parent if
 152    * unknown property).
 153    *
 154    * Template arguments:
 155    * @param FuncImp the class which implements this object's functions
 156    * @param ThisImp the class of "this". It must implement the getValueProperty(exec,token) method,
 157    * for non-function properties.
 158    * @param ParentImp the class of the parent, to propagate the lookup.
 159    *
 160    * Method arguments:
 161    * @param exec execution state, as usual
 162    * @param propertyName the property we're looking for
 163    * @param table the static hashtable for this class
 164    * @param thisObj "this"
 165    */
 166   template <class FuncImp, class ThisImp, class ParentImp>
 167   inline Value lookupGet(ExecState *exec, const Identifier &propertyName,
 168                          const HashTable* table, const ThisImp* thisObj)
 169   {
 170     const HashEntry* entry = Lookup::findEntry(table, propertyName);
 171
 172     if (!entry) // not found, forward to parent
 173       return thisObj->ParentImp::get(exec, propertyName);
 174
 175     //fprintf(stderr, "lookupGet: found value=%d attr=%d\n", entry->value, entry->attr);
 176     if (entry->attr & Function)
 177       return lookupOrCreateFunction<FuncImp>(exec, propertyName, thisObj, entry->value, entry->params, entry->attr);
 178     return thisObj->getValueProperty(exec, entry->value);
 179   }
 180
 181   /**
 182    * Simplified version of lookupGet in case there are only functions.
 183    * Using this instead of lookupGet prevents 'this' from implementing a dummy getValueProperty.
 184    */
 185   template <class FuncImp, class ParentImp>
 186   inline Value lookupGetFunction(ExecState *exec, const Identifier &propertyName,
 187                          const HashTable* table, const ObjectImp* thisObj)
 188   {
 189     const HashEntry* entry = Lookup::findEntry(table, propertyName);
 190
 191     if (!entry) // not found, forward to parent
 192       return static_cast<const ParentImp *>(thisObj)->ParentImp::get(exec, propertyName);
 193
 194     if (entry->attr & Function)
 195       return lookupOrCreateFunction<FuncImp>(exec, propertyName, thisObj, entry->value, entry->params, entry->attr);
 196
 197     fprintf(stderr, "Function bit not set! Shouldn't happen in lookupGetFunction!\n" );
 198     return Undefined();
 199   }
 200
 201   /**
 202    * Simplified version of lookupGet in case there are no functions, only "values".
 203    * Using this instead of lookupGet removes the need for a FuncImp class.
 204    */
 205   template <class ThisImp, class ParentImp>
 206   inline Value lookupGetValue(ExecState *exec, const Identifier &propertyName,
 207                            const HashTable* table, const ThisImp* thisObj)
 208   {
 209     const HashEntry* entry = Lookup::findEntry(table, propertyName);
 210
 211     if (!entry) // not found, forward to parent
 212       return thisObj->ParentImp::get(exec, propertyName);
 213
 214     if (entry->attr & Function)
 215       fprintf(stderr, "Function bit set! Shouldn't happen in lookupGetValue! propertyName was %s\n", propertyName.ascii() );
 216     return thisObj->getValueProperty(exec, entry->value);
 217   }
 218
 219   /**
 220    * This one is for "put".
 221    * Lookup hash entry for property to be set, and set the value.
 222    */
 223   template <class ThisImp, class ParentImp>
 224   inline void lookupPut(ExecState *exec, const Identifier &propertyName,
 225                         const Value& value, int attr,
 226                         const HashTable* table, const ThisImp* thisObj)
 227   {
 228     const HashEntry* entry = Lookup::findEntry(table, propertyName);
 229
 230     if (!entry) // not found: forward to parent
 231       thisObj->ParentImp::put(exec, propertyName, value, attr);
 232     else if (entry->attr & Function) // function: put as override property
 233       thisObj->ObjectImp::put(exec, propertyName, value, attr);
 234     else if (entry->attr & ReadOnly) // readonly! Can't put!
 235 #ifdef KJS_VERBOSE
 236       fprintf(stderr,"WARNING: Attempt to change value of readonly property '%s'\n",propertyName.ascii());
 237 #else
 238       ; // do nothing
 239 #endif
 240     else
 241       thisObj->putValueProperty(exec, entry->value, value, attr);
 242   }
 243
 244   /**
 245    * This template method retrieves or create an object that is unique
 246    * (for a given interpreter) The first time this is called (for a given
 247    * property name), the Object will be constructed, and set as a property
 248    * of the interpreter's global object. Later calls will simply retrieve
 249    * that cached object. Note that the object constructor must take 1 argument, exec.
 250    */
 251   template <class ClassCtor>
 252   inline ObjectImp *cacheGlobalObject(ExecState *exec, const Identifier &propertyName)
 253   {
 254     ObjectImp *globalObject = static_cast<ObjectImp *>(exec->lexicalInterpreter()->globalObject().imp());
 255     ValueImp *obj = globalObject->getDirect(propertyName);
 256     if (obj) {
 257       assert(obj->isObject());
 258       return static_cast<ObjectImp *>(obj);
 259     }
 260     ObjectImp *newObject = new ClassCtor(exec);
 261     globalObject->put(exec, propertyName, Value(newObject), Internal);
 262     return newObject;
 263   }
 264
 265   /**
 266    * Helpers to define prototype objects (each of which simply implements
 267    * the functions for a type of objects).
 268    * Sorry for this not being very readable, but it actually saves much copy-n-paste.
 269    * ParentProto is not our base class, it's the object we use as fallback.
 270    * The reason for this is that there should only be ONE DOMNode.hasAttributes (e.g.),
 271    * not one in each derived class. So we link the (unique) prototypes between them.
 272    *
 273    * Using those macros is very simple: define the hashtable (e.g. "DOMNodeProtoTable"), then
 274    * DEFINE_PROTOTYPE("DOMNode",DOMNodeProto)
 275    * IMPLEMENT_PROTOFUNC(DOMNodeProtoFunc)
 276    * IMPLEMENT_PROTOTYPE(DOMNodeProto,DOMNodeProtoFunc)
 277    * and use DOMNodeProto::self(exec) as prototype in the DOMNode constructor.
 278    * If the prototype has a "parent prototype", e.g. DOMElementProto falls back on DOMNodeProto,
 279    * then the last line will use IMPLEMENT_PROTOTYPE_WITH_PARENT, with DOMNodeProto as last argument.
 280    */
 281 #define DEFINE_PROTOTYPE(ClassName,ClassProto) \
 282   class ClassProto : public ObjectImp { \
 283     friend ObjectImp *cacheGlobalObject<ClassProto>(ExecState *exec, const Identifier &propertyName); \
 284   public: \
 285     static ObjectImp *self(ExecState *exec) \
 286     { \
 287       return cacheGlobalObject<ClassProto>( exec, "[[" ClassName ".prototype]]" ); \
 288     } \
 289   protected: \
 290     ClassProto( ExecState *exec ) \
 291       : ObjectImp( exec->lexicalInterpreter()->builtinObjectPrototype() ) {} \
 292     \
 293   public: \
 294     virtual const ClassInfo *classInfo() const { return &info; } \
 295     static const ClassInfo info; \
 296     Value get(ExecState *exec, const Identifier &propertyName) const; \
 297     bool hasProperty(ExecState *exec, const Identifier &propertyName) const; \
 298   }; \
 299   const ClassInfo ClassProto::info = { ClassName, 0, &ClassProto##Table, 0 };
 300
 301 #define IMPLEMENT_PROTOTYPE(ClassProto,ClassFunc) \
 302     Value ClassProto::get(ExecState *exec, const Identifier &propertyName) const \
 303     { \
 304       /*fprintf( stderr, "%sProto::get(%s) [in macro, no parent]\n", info.className, propertyName.ascii());*/ \
 305       return lookupGetFunction<ClassFunc,ObjectImp>(exec, propertyName, &ClassProto##Table, this ); \
 306     } \
 307     bool ClassProto::hasProperty(ExecState *exec, const Identifier &propertyName) const \
 308     { /*stupid but we need this to have a common macro for the declaration*/ \
 309       return ObjectImp::hasProperty(exec, propertyName); \
 310     }
 311
 312 #define IMPLEMENT_PROTOTYPE_WITH_PARENT(ClassProto,ClassFunc,ParentProto)  \
 313     Value ClassProto::get(ExecState *exec, const Identifier &propertyName) const \
 314     { \
 315       /*fprintf( stderr, "%sProto::get(%s) [in macro]\n", info.className, propertyName.ascii());*/ \
 316       Value val = lookupGetFunction<ClassFunc,ObjectImp>(exec, propertyName, &ClassProto##Table, this ); \
 317       if ( val.type() != UndefinedType ) return val; \
 318       /* Not found -> forward request to "parent" prototype */ \
 319       return ParentProto::self(exec)->get( exec, propertyName ); \
 320     } \
 321     bool ClassProto::hasProperty(ExecState *exec, const Identifier &propertyName) const \
 322     { \
 323       if (ObjectImp::hasProperty(exec, propertyName)) \
 324         return true; \
 325       return ParentProto::self(exec)->hasProperty(exec, propertyName); \
 326     }
 327
 328 #define IMPLEMENT_PROTOFUNC(ClassFunc) \
 329   class ClassFunc : public DOMFunction { \
 330   public: \
 331     ClassFunc(ExecState *exec, int i, int len) \
 332        : DOMFunction( /*proto? */ ), id(i) { \
 333        Value protect(this); \
 334        put(exec,lengthPropertyName,Number(len),DontDelete|ReadOnly|DontEnum); \
 335     } \
 336     /** You need to implement that one */ \
 337     virtual Value tryCall(ExecState *exec, Object &thisObj, const List &args); \
 338   private: \
 339     int id; \
 340   };
 341
 342   /*
 343    * List of things to do when porting an objectimp to the 'static hashtable' mechanism:
 344    * - write the hashtable source, between @begin and @end
 345    * - add a rule to build the .lut.h
 346    * - include the .lut.h
 347    * - mention the table in the classinfo (add a classinfo if necessary)
 348    * - write/update the class enum (for the tokens)
 349    * - turn get() into getValueProperty(), put() into putValueProperty(), using a switch and removing funcs
 350    * - write get() and/or put() using a template method
 351    * - cleanup old stuff (e.g. hasProperty)
 352    * - compile, test, commit ;)
 353    */
 354 }; // namespace
 355
 356 #endif