/* 

 *   Copyright (c) 2000, 2002 Michael J. Roberts.  All Rights Reserved.

 *   

 *   Please see the accompanying license file, LICENSE.TXT, for information

 *   on using and copying this software.  

 */

/*

Name

  vmdict.h - VM 'Dictionary' metaclass

Function

Notes

Modified

  01/24/00 MJRoberts  - Creation

*/

#ifndef VMDICT_H

#define VMDICT_H

#include <stdlib.h>

#include <string.h>

#include "t3std.h"

#include "vmtype.h"

#include "vmglob.h"

#include "vmobj.h"

#include "vmundo.h"

#include "vmhash.h"

/* forward-declare the class */

class CVmObjDict;

/* ------------------------------------------------------------------------ */

/* 

 *   undo action codes 

 */

enum dict_undo_action

{

    /* we added this word to the dictionary (undo by deleting it) */

    DICT_UNDO_ADD,

    /* we deleted this word from the dictionary (undo by adding it back) */

    DICT_UNDO_DEL,

    /* we change the comparator object */

    DICT_UNDO_COMPARATOR

};

/* ------------------------------------------------------------------------ */

/*

 *   The image file data block is arranged as follows:

 *   

 *.  UINT4 comparator_object_id

 *.  UINT2 load_image_entry_count

 *.  entry 1

 *.  entry 2

 *.  ...

 *.  entry N

 *   

 *   Each entry has the following structure:

 *   

 *.  UCHAR key_string_byte_length

 *.  key_string (UTF-8 characters, not null terminated, XOR'ed with 0xBD)

 *.  UINT2 number of sub-entries

 *.  sub-entry 1

 *.  sub-entry 2

 *.  etc

 *   

 *   Each sub-entry is structured like this:

 *   

 *   UINT4 associated_object_id

 *.  UINT2 defining_property_id

 *   

 *   Note that each byte of the key string is XOR'ed with the arbitrary

 *   byte value 0xBD.  This is simply to provide a minimal level of

 *   obfuscation in the image file to prevent casual browsing of the image

 *   contents.  

 */

/*   

 *   Separately, we maintain a hash table and entries in the hash table.

 *   We don't attempt to keep any of the other data in the object in a

 *   portable internal format, but rather serialize data to a saved state

 *   file and rebuild the internal format on demand.  We also do not keep

 *   the hash table in the variable heap mechanism, but simply use the

 *   standard system heap.  The internal structure of our hash table would

 *   be too complicated to keep in the variable heap in portable format,

 *   and furthermore we do not expect dictionary instances to be numerous

 *   (hence the cost of serializing should be small, since it won't be

 *   repeated over many objects) or frequently changed (hence keeping

 *   these in the standard system heap should not cause excessive heap

 *   fragmentation).

 */

/* comparator object types */

enum vm_dict_comp_type

{

    VMDICT_COMP_NONE,                               /* no comparator object */

    VMDICT_COMP_STRCOMP,                                /* StringComparator */

    VMDICT_COMP_GENERIC                        /* generic comparator object */

};

/*

 *   Dictionary object extension - we use this memory (in the variable

 *   heap) to keep track of our image data and our hash table.  

 */

struct vm_dict_ext

{

    /* pointer to load image data, if any */

    const char *image_data_;

    size_t image_data_size_;

    /* pointer to our hash table (in the system heap) */

    class CVmHashTable *hashtab_;

    /* flag: the table has been changed since image load */

    ulong modified_;

    /* our comparator object, if any */

    vm_obj_id_t comparator_;

    CVmObject *comparator_obj_;

    /* type of comparator */

    vm_dict_comp_type comparator_type_;

};

/* ------------------------------------------------------------------------ */

/*

 *   Dictionary object interface 

 */

class CVmObjDict: public CVmObject

{

    friend class CVmMetaclassDict;

public:

    /* metaclass registration object */

    static class CVmMetaclass *metaclass_reg_;

    class CVmMetaclass *get_metaclass_reg() const { return metaclass_reg_; }

    /* am I of the given metaclass? */

    virtual int is_of_metaclass(class CVmMetaclass *meta) const

    {

        /* try my own metaclass and my base class */

        return (meta == metaclass_reg_

                || CVmObject::is_of_metaclass(meta));

    }

    /* create dynamically using stack arguments */

    static vm_obj_id_t create_from_stack(VMG_ const uchar **pc_ptr,

                                         uint argc);

    /* 

     *   call a static property - we don't have any of our own, so simply

     *   "inherit" the base class handling 

     */

    static int call_stat_prop(VMG_ vm_val_t *result,

                              const uchar **pc_ptr, uint *argc,

                              vm_prop_id_t prop)

        { return CVmObject::call_stat_prop(vmg_ result, pc_ptr, argc, prop); }

    /* determine if an object is a Dictionary object */

    static int is_dictionary_obj(VMG_ vm_obj_id_t obj)

        { return vm_objp(vmg_ obj)->is_of_metaclass(metaclass_reg_); }

    /* notify of deletion */

    void notify_delete(VMG_ int in_root_set);

    /* get a property */

    int get_prop(VMG_ vm_prop_id_t prop, vm_val_t *val,

                 vm_obj_id_t self, vm_obj_id_t *source_obj, uint *argc);

    /* set a property */

    void set_prop(VMG_ class CVmUndo *undo,

                  vm_obj_id_t self, vm_prop_id_t prop, const vm_val_t *val);

    /* receive notification of a new undo savepoint */

    void notify_new_savept() { }

    /* apply undo */

    void apply_undo(VMG_ struct CVmUndoRecord *rec);

    /* discard additional information associated with an undo record */

    void discard_undo(VMG_ struct CVmUndoRecord *rec);

    /* mark a reference in undo */

    void mark_undo_ref(VMG_ struct CVmUndoRecord *rec);

    /* remove stale weak references from an undo record */

    void remove_stale_undo_weak_ref(VMG_ struct CVmUndoRecord *rec);

    /* mark references */

    void mark_refs(VMG_ uint);

    /* remove weak references */

    void remove_stale_weak_refs(VMG0_);

    /* load from an image file */

    void load_from_image(VMG_ vm_obj_id_t, const char *ptr, size_t siz);

    /* perform post-load initialization */

    void post_load_init(VMG_ vm_obj_id_t self);

    /* restore to image file state */

    void reset_to_image(VMG_ vm_obj_id_t /*self*/);

    /* determine if the object has been changed since it was loaded */

    int is_changed_since_load() const;

    /* save to a file */

    void save_to_file(VMG_ class CVmFile *fp);

    /* restore from a file */

    void restore_from_file(VMG_ vm_obj_id_t self,

                           class CVmFile *fp, class CVmObjFixup *);

    /* rebuild for image file */

    virtual ulong rebuild_image(VMG_ char *buf, ulong buflen);

    /* convert to constant data */

    virtual void convert_to_const_data(VMG_ class CVmConstMapper *mapper,

                                       vm_obj_id_t self);

    /* enumerate the properties for which a word is defined */

    void enum_word_props(VMG_ void (*cb_func)(VMG_ void *, vm_prop_id_t,

                                              const vm_val_t *),

                         void *cb_ctx, const vm_val_t *strval,

                         const char *strp, size_t strl);

    /* get/set my comparator object */

    vm_obj_id_t get_comparator() const { return get_ext()->comparator_; }

    void set_comparator(VMG_ vm_obj_id_t obj);

    /* 

     *   Match a pair of strings.

     *   

     *   'valstrval' is the vm_val_t with the string value, if one is

     *   available; if not, this can be given as null and we'll synthesize a

     *   new string object from 'valstr' and 'vallen' if one is needed.  We

     *   don't require the caller to synthesize a string object because we

     *   might not need one; we'll create one only if one is actually needed.

     *   

     *   'valstr' and 'vallen' directly give the text of the value string,

     *   and 'refstr' and 'reflen' likewise directly give the text of the

     *   reference string.  

     */

    int match_strings(VMG_ const vm_val_t *valstrval,

                      const char *valstr, size_t vallen,

                      const char *refstr, size_t reflen,

                      vm_val_t *result_val);

    /* 

     *   Calculate the hash value for a string.  As in match_strings(),

     *   'valstrval' can be passed as null if no vm_val_t for the string text

     *   is available, in which case we'll synthesize a new string object

     *   from 'valstr' and 'vallen' if one is needed. 

     */

    unsigned int calc_str_hash(VMG_ const vm_val_t *valstrval,

                               const char *valstr, size_t vallen);

protected:

    CVmObjDict(VMG0_);

    /* set the comparator type */

    void set_comparator_type(VMG_ vm_obj_id_t obj);

    /* create or re-create the hash table */

    void create_hash_table(VMG0_);

    /* fill the hash table with entries from the image data */

    void build_hash_from_image(VMG0_);

    /* property evaluation - undefined property */

    int getp_undef(VMG_ vm_obj_id_t, vm_val_t *, uint *) { return FALSE; }

    /* enumeration callback for getp_find */

    static void find_cb(void *ctx, class CVmHashEntry *entry);

    /* enumeration callback for getp_isdef */

    static void isdef_cb(void *ctx, class CVmHashEntry *entry);

    /* enumeration callback for enum_word_props */

    static void enum_word_props_cb(void *ctx, class CVmHashEntry *entry);

    /* property evaluation - set the comparator object */

    int getp_set_comparator(VMG_ vm_obj_id_t, vm_val_t *val, uint *argc);

    /* property evaluation - findWord */

    int getp_find(VMG_ vm_obj_id_t, vm_val_t *val, uint *argc);

    /* property evaluation - addWord */

    int getp_add(VMG_ vm_obj_id_t self, vm_val_t *val, uint *argc);

    /* service routine for getp_add - add a single string */

    void getp_add_string(VMG_ vm_obj_id_t self,

                         const char *str, vm_obj_id_t obj,

                         vm_prop_id_t voc_prop);

    /* property evaluation - delWord */

    int getp_del(VMG_ vm_obj_id_t self, vm_val_t *val, uint *argc);

    /* service routine for getp_del - remove a single string */

    void getp_del_string(VMG_ vm_obj_id_t self,

                         const char *str, vm_obj_id_t obj,

                         vm_prop_id_t voc_prop);

    /* property evaluation - isWordDefined */

    int getp_is_defined(VMG_ vm_obj_id_t self, vm_val_t *val, uint *argc);

    /* property evaluation - forEachWord */

    int getp_for_each_word(VMG_ vm_obj_id_t self, vm_val_t *retval,

                           uint *argc);

    /* get my extension, properly cast */

    vm_dict_ext *get_ext() const { return (vm_dict_ext *)ext_; }

    /* 

     *   add an entry; returns true if successful, false if the entry

     *   already exists, in which case no new entry is made 

     */

    int add_hash_entry(VMG_ const char *p, size_t len, int copy,

                       vm_obj_id_t obj, vm_prop_id_t prop, int from_image);

    /* delete an entry */

    int del_hash_entry(VMG_ const char *p, size_t len,

                       vm_obj_id_t obj, vm_prop_id_t prop);

    /* callback for hash table enumeration - delete stale weak refs */

    static void remove_weak_ref_cb(void *ctx, class CVmHashEntry *entry);

    /* callback for hash table enumeration - save file */

    static void save_file_cb(void *ctx, class CVmHashEntry *entry);

    /* callback for hash table enumeration - convert to constant data */

    static void cvt_const_cb(void *ctx, class CVmHashEntry *entry);

    /* callback for hash table enumeration - rebuild image, phase 1 */

    static void rebuild_cb_1(void *ctx, class CVmHashEntry *entry);

    /* callback for hash table enumeration - rebuild image, phase 2 */

    static void rebuild_cb_2(void *ctx, class CVmHashEntry *entry);

    /* allocate an undo record */

    struct dict_undo_rec *alloc_undo_rec(enum dict_undo_action action,

                                         const char *txt, size_t len);

    /* add a record to the global undo stream */

    void add_undo_rec(VMG_ vm_obj_id_t self, struct dict_undo_rec *rec);

    /* function table */

    static int (CVmObjDict::*func_table_[])(VMG_ vm_obj_id_t self,

                                            vm_val_t *retval, uint *argc);

};

/* ------------------------------------------------------------------------ */

/*

 *   hash table list entry - each hash entry has a list of associated

 *   objects; this structure represents an entry in one of these lists 

 */

struct vm_dict_entry

{

    vm_dict_entry(vm_obj_id_t obj, vm_prop_id_t prop, int from_image)

    {

        obj_ = obj;

        prop_ = prop;

        from_image_ = from_image;

        nxt_ = 0;

    }

    /* object ID of this entry */

    vm_obj_id_t obj_;

    /* defining property ID */

    vm_prop_id_t prop_;

    /* next entry in the list */

    vm_dict_entry *nxt_;

    /* flag: entry is from the image file */

    int from_image_;

};

/*

 *   Dictionary object hash table entry 

 */

class CVmHashEntryDict: public CVmHashEntryCS

{

public:

    CVmHashEntryDict(const char *str, size_t len, int copy, int from_image)

        : CVmHashEntryCS(str, len, copy || from_image)

    {

        /* nothing in our item list yet */

        list_ = 0;

    }

    ~CVmHashEntryDict()

    {

        /* delete all of our entries */

        while (list_ != 0)

        {

            vm_dict_entry *nxt;

            /* note the next entry */

            nxt = list_->nxt_;

            /* delete the current entry */

            delete list_;

            /* move on to the next entry */

            list_ = nxt;

        }

    }

    /* get the first entry in our list */

    vm_dict_entry *get_head() const { return list_; }

    /* 

     *   add an entry to our list - returns true if we added the entry,

     *   false if an entry with the same object ID was already present, in

     *   which case we will ignore the addition 

     */

    int add_entry(vm_obj_id_t obj, vm_prop_id_t prop, int from_image)

    {

        vm_dict_entry *entry;

        vm_dict_entry *prv;

        /* 

         *   check to see if this entry is already in our list - if it is,

         *   don't bother adding the redundant definition 

         */

        for (prv = 0, entry = list_ ; entry != 0 ; entry = entry->nxt_)

        {

            /* 

             *   if this entry matches the object ID and property ID,

             *   ignore the addition 

             */

            if (entry->obj_ == obj && entry->prop_ == prop)

                return FALSE;

            /* 

             *   if this entry matches the property, remember it as the

             *   insertion point, so that we keep all definitions for the

             *   same word with the same property together in the list 

             */

            if (entry->prop_ == prop)

                prv = entry;

        }

        /* create a list entry */

        entry = new vm_dict_entry(obj, prop, from_image);

        /* 

         *   link it in after the insertion point, or at the head of our

         *   list if we didn't find any other insertion point 

         */

        if (prv != 0)

        {

            /* we found an insertion point - link it in */

            entry->nxt_ = prv->nxt_;

            prv->nxt_ = entry;

        }

        else

        {

            /* no insertion point - link it at the head of our list */

            entry->nxt_ = list_;

            list_ = entry;

        }

        /* we added the entry */

        return TRUE;

    }

    /* 

     *   Delete all entries matching a given object ID from our list.

     *   Returns true if any entries were deleted, false if not. 

     */

    int del_entry(CVmHashTable *table, vm_obj_id_t obj, vm_prop_id_t prop)

    {

        vm_dict_entry *cur;

        vm_dict_entry *nxt;

        vm_dict_entry *prv;

        int found;

        /* find the entry in our list */

        for (found = FALSE, prv = 0, cur = list_ ; cur != 0 ;

             prv = cur, cur = nxt)

        {

            /* remember the next entry */

            nxt = cur->nxt_;

            /* if this is our entry, delete it */

            if (cur->obj_ == obj && cur->prop_ == prop)

            {

                /* unlink this entry */

                if (prv != 0)

                    prv->nxt_ = nxt;

                else

                    list_ = nxt;

                /* delete this entry */

                delete cur;

                /* note that we found at least one entry to delete */

                found = TRUE;

            }

        }

        /* if our list is now empty, delete myself from the table */

        if (list_ == 0)

        {

            /* remove myself from the table */

            table->remove(this);

            /* delete myself */

            delete this;

        }

        /* tell the caller whether we found anything to delete */

        return found;

    }

protected:

    /* list of associated objects */

    vm_dict_entry *list_;

};

/* ------------------------------------------------------------------------ */

/*

 *   Registration table object 

 */

class CVmMetaclassDict: public CVmMetaclass

{

public:

    /* get the global name */

    const char *get_meta_name() const { return "dictionary2/030000"; }

    /* create from image file */

    void create_for_image_load(VMG_ vm_obj_id_t id)

        { new (vmg_ id) CVmObjDict(vmg0_); }

    /* create from restoring from saved state */

    void create_for_restore(VMG_ vm_obj_id_t id)

        { new (vmg_ id) CVmObjDict(vmg0_); }

    /* create dynamically using stack arguments */

    vm_obj_id_t create_from_stack(VMG_ const uchar **pc_ptr, uint argc)

        { return CVmObjDict::create_from_stack(vmg_ pc_ptr, argc); }

    /* call a static property */

    int call_stat_prop(VMG_ vm_val_t *result,

                       const uchar **pc_ptr, uint *argc,

                       vm_prop_id_t prop)

    {

        return CVmObjDict::call_stat_prop(vmg_ result, pc_ptr, argc, prop);

    }

};

#endif /* VMDICT_H */

/*

 *   Register the class 

 */