/*-
 * See the file LICENSE for redistribution information.
 *
 * Copyright (c) 2002-2006
 *      Sleepycat Software.  All rights reserved.
 *
 * $Id: Format.java,v 1.20 2006/05/24 20:00:49 mark Exp $
 */

package com.sleepycat.persist.impl;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.sleepycat.persist.model.ClassMetadata;
import com.sleepycat.persist.model.EntityMetadata;
import com.sleepycat.persist.model.PrimaryKeyMetadata;
import com.sleepycat.persist.model.SecondaryKeyMetadata;
import com.sleepycat.persist.raw.RawField;
import com.sleepycat.persist.raw.RawType;

/**
 * The base class for all object formats.  Formats are used to define the
 * stored layout for all persistent classes, including simple types.
 *
 * The design documentation below describes the storage format for entities and
 * its relationship to information stored per format in the catalog.
 *
 * Requirements
 * ------------
 * + Provides EntityBinding for objects and EntryBinding for keys.
 * + Provides SecondaryKeyCreator, SecondaryMultiKeyCreator and
 *   SecondaryMultiKeyNullifier (SecondaryKeyNullifier is redundant).
 * + Works with reflection and bytecode enhancement.
 * + For reflection only, works with any entity model not just annotations.
 * + Bindings are usable independently of the persist API.
 * + Performance is almost equivalent to hand coded tuple bindings.
 * + Small performance penalty for compatible class changes (new fields,
 *   widening).
 * + Secondary key create/nullify do not have to deserialize the entire record;
 *   in other words, store secondary keys at the start of the data.
 *
 * Class Format
 * ------------
 * Every distinct class format is given a unique format ID.  Class IDs are not
 * equivalent to class version numbers (as in the version property of @Entity
 * and @Persistent) because the format can change when the version number does
 * not.  Changes that cause a unique format ID to be assigned are:
 *
 * + Add field.
 * + Widen field type.
 * + Change primitive type to primitive wrapper class.
 * + Add or drop secondary key.
 * + Any incompatible class change.
 *
 * The last item, incompatible class changes (see Mutations), also correspond
 * to a class version change.
 *
 * For each distinct class format the following information is conceptually
 * stored in the catalog, keyed by format ID.
 *
 * - Class name
 * - Class version number
 * - Superclass format
 * - Kind: simple, enum, complex, array
 * - For kind == simple:
 *     - Primitive class
 * - For kind == enum:
 *     - Array of constant names, sorted by name.
 * - For kind == complex:
 *     - Primary key fieldInfo, or null if no primary key is declared
 *     - Array of secondary key fieldInfo, sorted by field name
 *     - Array of other fieldInfo, sorted by field name
 * - For kind == array:
 *     - Component class format
 *     - Number of array dimensions
 * - Other metadata for RawType
 *
 * Where fieldInfo is:
 *     - Field name
 *     - Field class
 *     - Other metadata for RawField
 *
 * Data Layout
 * -----------
 * For each entity instance the data layout is as follows:
 *
 *   instanceData: formatId keyFields... nonKeyFields...
 *   keyFields:    fieldValue...
 *   nonKeyFields: fieldValue...
 *
 * The formatId is the (positive non-zero) ID of a class format, defined above.
 * This is ID of the most derived class of the instance.  It is stored as a
 * packed integer.
 *
 * Following the format ID, zero or more sets of secondary key field values
 * appear, followed by zero or more sets of other class field values.
 *
 * The keyFields are the sets of secondary key fields for each class in order
 * of the highest superclass first.  Within a class, fields are ordered by
 * field name.
 *
 * The nonKeyFields are the sets of other non-key fields for each class in
 * order of the highest superclass first.  Within a class, fields are ordered
 * by field name.
 *
 * A field value is:
 *
 *   fieldValue:   primitiveValue
 *               | nullId
 *               | instanceRef
 *               | instanceData
 *               | simpleValue
 *               | enumValue
 *               | arrayValue
 *
 * For a primitive type, a primitive value is used as defined for tuple
 * bindings.  For float and double, sorted float and sorted double tuple values
 * are used.
 *
 * For a non-primitive type with a null value, a nullId is used that has a zero
 * (illegal formatId) value.  This includes String and other simple reference
 * types.  The formatId is stored as a packed integer, meaning that it is
 * stored as a single zero byte.
 *
 * For a non-primitive type, an instanceRef is used for a non-null instance
 * that appears earlier in the data byte array.  An instanceRef is the negation
 * of the byte offset of the instanceData that appears earlier.  It is stored
 * as a packed integer.
 *
 * The remaining rules apply only to reference types with non-null values that
 * do not appear earlier in the data array.
 *
 * For an array type, an array formatId is used that identifies the component
 * type and the number of array dimensions.  This is followed by an array
 * length (stored as a packed integer) and zero or more fieldValue elements.
 * For an array with N+1 dimensions where N is greater than zero, the leftmost
 * dimension is enumerated such that each fieldValue element is itself an array
 * of N dimensions or null.
 *
 *   arrayValue:  formatId length fieldValue...
 *
 * For an enum type, an enumValue is used, consisting of a formatId that
 * identifies the enum class and an enumIndex (stored as a packed integer) that
 * identifies the constant name in the enum constant array of the enum class
 * format:
 *
 *   enumValue:   formatId enumIndex
 *
 * For a simple type, a simpleValue is used.  This consists of the formatId
 * that identifies the class followed by the simple type value.  For a
 * primitive wrapper type the simple type value is the corresponding primitive,
 * for a Date it is the milliseconds as a long primitive, and for BigInteger or
 * BigDecimal it is a byte array as defined for tuple bindings of these types.
 *
 *   simpleValue: formatId value
 *
 * For all other complex types, an instanceData is used, which is defined
 * above.
 *
 * Secondary Keys
 * --------------
 * For secondary key support we must account for writing and nullifying
 * specific keys.  Rather than instantiating the entity and then performing
 * the secondary key operation, we strive to perform the secondary key
 * operation directly on the byte format.
 *
 * To create a secondary key we skip over other fields and then copy the bytes
 * of the embedded key.  This approach is very efficient because a) the entity
 * is not instantiated, and b) the secondary keys are stored at the beginning
 * of the byte format and can be quickly read.
 *
 * To nullify we currently instantiate the raw entity, set the key field to null
 * (or remove it from the array/collection), and convert the raw entity back to
 * bytes.  Although the performance of this approach is not ideal because it
 * requires serialization, it avoids the complexity of modifying the packed
 * serialized format directly, adjusting references to key objects, etc.  Plus,
 * when we nullify a key we are going to write the record, so the serialization
 * overhead may not be significant.  For the record, I tried implementing
 * nullification of the bytes directly and found it was much too complex.
 *
 * Lifecycle
 * ---------
 * Format are managed by a Catalog class.  Simple formats are managed by
 * SimpleCatalog, and are copied from the SimpleCatalog by PersistCatalog.
 * Other formats are managed by PersistCatalog.  The lifecycle of a format
 * instance is:
 *
 * - Constructed by the catalog when a format is requested for a Class
 *   that currently has no associated format.
 *
 * - The catalog calls setId() and adds the format to its format list
 *   (indexed by format id) and map (keyed by class name).
 *
 * - The catalog calls collectRelatedFormats(), where a format can create
 *   additional formats that it needs, or that should also be persistent.
 *
 * - The catalog calls initializeIfNeeded(), which calls the initialize()
 *   method of the format class.
 *
 * - initialize() should initialize any transient fields in the format.
 *   initialize() can assume that all related formats are available in the
 *   catalog.  It may call initializeIfNeeded() for those related formats, if
 *   it needs to interact with an initialized related format; this does not
 *   cause a cycle, because initializeIfNeeded() does nothing for an already
 *   initialized format.
 *
 * - The catalog creates a group of related formats at one time, and then
 *   writes its entire list of formats to the catalog DB as a single record.
 *   This grouping reduces the number of writes.
 *
 * - When a catalog is opened and the list of existing formats is read.  After
 *   a format is deserialized, its initializeIfNeeded() method is called.
 *   setId() and collectRelatedFormats() are not called, since the ID and
 *   related formats are stored in serialized fields.
 *
 * - There are two modes for opening an existing catalog: raw mode and normal
 *   mode.  In raw mode, the old format is used regardless of whether it
 *   matches the current class definition; in fact the class is not accessed
 *   and does not need to be present.
 *
 * - In normal mode, for each existing format that is initialized, a new format
 *   is also created based on the current class and metadata definition.  If
 *   the two formats are equal, the new format is discarded.  If they are
 *   unequal, the new format becomes the current format and the old format's
 *   evolveTo(newFormat) method is called.  evolveTo() is responsible for
 *   adjusting the old format for class evolution.  Any number of non-current
 *   formats may exist for a given class, and are setup to evolve the single
 *   current format for the class.
 *
 * @author Mark Hayes
 */
public abstract class Format implements RawType, Serializable {

    private static final long serialVersionUID = 545633644568489850L;

    /** Null reference. */
    static final int ID_NULL     = 0;
    /** Object */
    static final int ID_OBJECT   = 1;
    /** Boolean */
    static final int ID_BOOL     = 2;
    static final int ID_BOOL_W   = 3;
    /** Byte */
    static final int ID_BYTE     = 4;
    static final int ID_BYTE_W   = 5;
    /** Short */
    static final int ID_SHORT    = 6;
    static final int ID_SHORT_W  = 7;
    /** Integer */
    static final int ID_INT      = 8;
    static final int ID_INT_W    = 9;
    /** Long */
    static final int ID_LONG     = 10;
    static final int ID_LONG_W   = 11;
    /** Float */
    static final int ID_FLOAT    = 12;
    static final int ID_FLOAT_W  = 13;
    /** Double */
    static final int ID_DOUBLE   = 14;
    static final int ID_DOUBLE_W = 15;
    /** Character */
    static final int ID_CHAR     = 16;
    static final int ID_CHAR_W   = 17;
    /** String */
    static final int ID_STRING   = 18;
    /** BigInteger */
    static final int ID_BIGINT   = 19;
    /** BigDecimal */
    static final int ID_BIGDEC   = 20;
    /** Date */
    static final int ID_DATE     = 21;

    /** First simple type. */
    static final int ID_SIMPLE_MIN  = 2;
    /** Last simple type. */
    static final int ID_SIMPLE_MAX  = 21;
    /** Last predefined ID, after which dynamic IDs are assigned. */
    static final int ID_PREDEFINED  = 30;

    static boolean isPredefined(Format format) {
        return format.getId() <= ID_PREDEFINED;
    }

    private int id;
    private String className;
    private int version;
    private Format superFormat;
    private Set<String> supertypes;
    private transient Class type;
    private transient Format evolveToFormat;
    private transient Format proxiedFormat;
    private transient boolean initialized;

    /**
     * Creates a new format for a given class.
     */
    Format(Class type) {
        this.type = type;
        className = type.getName();
        supertypes = new HashSet<String>();
        addSupertypes();
    }

    /**
     * Returns the format ID.
     */
    final int getId() {
        return id;
    }

    /**
     * Called by the Catalog to set the format ID when a new format is added to
     * the format list, before calling initializeIfNeeded().
     */
    final void setId(int id) {
        this.id = id;
    }

    /**
     * Returns the class that this format represents.  This method should not
     * be called in rawAccess mode, or for an unevolved format.
     */
    final Class getType() {
        return type;
    }

    /**
     * Returns the format of the superclass.
     */
    final Format getSuperFormat() {
        return superFormat;
    }

    /**
     * Called to set the format of the superclass during initialize().
     */
    final void setSuperFormat(Format superFormat) {
        this.superFormat = superFormat;
    }

    /**
     * Returns the format that is proxied by this format.  If non-null is
     * returned, then this format is a PersistentProxy.
     */
    final Format getProxiedFormat() {
        return proxiedFormat;
    }

    /**
     * Called by ProxiedFormat to set the proxied format.
     */
    final void setProxiedFormat(Format proxiedFormat) {
        this.proxiedFormat = proxiedFormat;
    }

    /**
     * Called by the Catalog to initialize a format, and may also be called
     * during initialize() for a related format to ensure that the related
     * format is initialized.  This latter case is allowed to support
     * bidirectional dependencies.  This method will do nothing if the format
     * is already intialized.
     */
    final void initializeIfNeeded(Catalog catalog) {
        if (!initialized) {
            try {
                type = SimpleCatalog.classForName(className);
            } catch (ClassNotFoundException e) {
                throw new IllegalStateException(e);
            }
            initialize(catalog);
            initialized = true;
        }
    }

    /**
     * Adds all interfaces and superclasses to the supertypes set.
     */
    private void addSupertypes() {
        addInterfaces(type);
        Class stype = type.getSuperclass();
        while (stype != null && stype != Object.class) {
            supertypes.add(stype.getName());
            addInterfaces(stype);
            stype = stype.getSuperclass();
        }
    }

    /**
     * Recursively adds interfaces to the supertypes set.
     */
    private void addInterfaces(Class cls) {
        Class[] interfaces = cls.getInterfaces();
        for (Class iface : interfaces) {
            if (iface != Enhanced.class) {
                supertypes.add(iface.getName());
                addInterfaces(iface);
            }
        }
    }

    /**
     * Called for an existing format that does not equal the current format for
     * the same class.  This format must be setup to evolve to the new format.
     */
    Format evolveTo(Format newFormat) {
        evolveToFormat = newFormat;
        return this;
    }

    /**
     * Returns whether this format is the current format for its class.  If
     * false is returned, this format is setup to evolve to the current format.
     */
    boolean isCurrentVersion() {
        return evolveToFormat == null;
    }

    /* -- Start of RawType interface methods. -- */

    public String getClassName() {
        return className;
    }

    public int getVersion() {
        return version;
    }

    public Format getSuperType() {
        return superFormat;
    }

    /* -- RawType methods that are overridden as needed in subclasses. -- */

    public boolean isSimple() {
        return false;
    }

    public boolean isPrimitive() {
        return false;
    }

    public boolean isEnum() {
        return false;
    }

    public List<String> getEnumConstants() {
        return null;
    }

    public boolean isArray() {
        return false;
    }

    public int getDimensions() {
        return 0;
    }

    public Format getComponentType() {
        return null;
    }

    public Map<String,RawField> getFields() {
        return null;
    }

    /* -- End of RawType methods. -- */

    /* -- Methods that may optionally be overridden by subclasses. -- */

    /**
     * Called by EntityOutput in rawAccess mode to determine whether an object
     * type is allowed to be assigned to a given field type.
     */
    boolean isAssignableTo(Format format) {
        if (proxiedFormat != null) {
            return proxiedFormat.isAssignableTo(format);
        } else {
            return format == this || 
                   format.id == ID_OBJECT ||
                   supertypes.contains(format.getClassName());
        }
    }

    /**
     * For primitive types only, returns their associated wrapper type.
     */
    Format getWrapperFormat() {
        return null;
    }

    /**
     * Returns whether this format class is an entity class.
     */
    boolean isEntity() {
        return false;
    }

    /**
     * Returns whether this class is present in the EntityModel.  Returns false
     * for a simple type, array type, or enum type.
     */
    boolean isModelClass() {
        return false;
    }

    /**
     * Returns the original model class metadata used to create this class, or
     * null if this is not a model class.
     */
    ClassMetadata getClassMetadata() {
        return null;
    }

    /**
     * Returns the original model entity metadata used to create this class, or
     * null if this is not an entity class.
     */
    EntityMetadata getEntityMetadata() {
        return null;
    }

    /**
     * For an entity class or subclass, returns the base entity class; returns
     * null in other cases.
     */
    Format getEntityFormat() {
        return null;
    }

    /**
     * Used to compare the current version and an old version, to determine
     * whether class evolution is needed.  Subclasses should always override
     * this method and also call super.equals() as part of their comparison.
     */
    @Override
    public boolean equals(Object other) {
        if (other instanceof Format) {
            Format o = (Format) other;
            if (superFormat != null) {
                if (o.superFormat == null ||
                    !superFormat.getClassName().equals
                        (o.superFormat.getClassName())) {
                    return false;
                }
            } else {
                if (o.superFormat != null) {
                    return false;
                }
            }
            boolean equalSupertypes = supertypes.equals(o.supertypes);
            if (!equalSupertypes) {
                /* Exclude Enhanced interface in old format. [#14651] */
                o.supertypes.remove(Enhanced.class.getName());
                equalSupertypes = supertypes.equals(o.supertypes);
            }
            return version == o.version &&
                   className.equals(o.className) &&
                   equalSupertypes;
        } else {
            return false;
        }
    }

    /* -- Abstract methods that must be implemented by subclasses. -- */

    /**
     * Initializes an uninitialized format, initializing its related formats
     * (superclass formats and array component formats) first.
     */
    abstract void initialize(Catalog catalog);

    /**
     * Calls catalog.createFormat for formats that this format depends on, or
     * that should also be persistent.
     */
    abstract void collectRelatedFormats(Catalog catalog,
                                        Map<String,Format> newFormats);

    /*
     * The remaining methods are used to read objects from data bytes via
     * EntityInput, and to write objects as data bytes via EntityOutput.
     * Ultimately these methods call methods in the Accessor interface to
     * get/set fields in the object.  Most methods have a rawAccess parameter
     * that determines whether the object is a raw object or a real persistent
     * object.
     *
     * The first group of methods are abstract and must be implemented by
     * format classes.  The second group have default implementations that
     * throw UnsupportedOperationException and may optionally be overridden.
     */
    
    /**
     * Creates an array of the format's class of the given length, as if
     * Array.newInstance(getType(), len) were called.  Formats implement this
     * method for specific classes, or call the accessor, to avoid the
     * reflection overhead of Array.newInstance.
     */
    abstract Object newArray(int len);

    /**
     * Creates a new instance of the target class using its default
     * constructor.  Normally this creates an empty object, and readObject() is
     * called next to fill in the contents.  This is done in two steps to allow
     * the instance to be registered by EntityInput before reading the
     * contents.  This allows the fields in an object or a nested object to
     * refer to the parent object in a graph.
     *
     * Alternatively, this method may read all or the first portion of the
     * data, rather than that being done by readObject().  This is required for
     * simple types and enums, where the object cannot be created without
     * reading the data.  In these cases, there is no possibility that the
     * parent object will be referenced by the child object in the graph.  It
     * should not be done in other cases, or the graph references may not be
     * maintained faithfully.
     */
    abstract Object newInstance(EntityInput input, boolean rawAccess);

    /**
     * Called after newInstance() to read the rest of the data bytes and fill
     * in the object contents.  If the object was read completely by
     * newInstance(), this method does nothing.
     */
    abstract void readObject(Object o, EntityInput input, boolean rawAccess);

    /**
     * Writes a given instance of the target class to the output data bytes.
     * This is the complement of the newInstance()/readObject() pair.
     */
    abstract void writeObject(Object o, EntityOutput output, boolean rawAccess);

    /**
     * Skips over the object's contents, as if readObject() were called, but
     * without returning an object.  Used for extracting secondary key bytes
     * without having to instantiate the object.  For reference types, the
     * format ID is read just before calling this method, so this method is
     * responsible for skipping everything following the format ID.
     */
    abstract void skipContents(EntityInput input);

    /**
     * When extracting a secondary key, called to skip over all fields up to
     * the given secondary key field.  Returns the format of the key field
     * found, or null if the field is not present (nullified) in the object.
     */
    Format skipToSecKey(EntityInput input, String keyName) {
        throw new UnsupportedOperationException(className);
    }

    /**
     * Called after skipToSecKey() to copy the data bytes of a singular
     * (XXX_TO_ONE) key field.
     */
    void copySecKey(EntityInput input, EntityOutput output) {
        throw new UnsupportedOperationException(className);
    }

    /**
     * Called after skipToSecKey() to copy the data bytes of an array or
     * collection (XXX_TO_MANY) key field.
     */
    void copySecMultiKey(EntityInput input, Format keyFormat, Set results) {
        throw new UnsupportedOperationException(className);
    }

    /**
     * Nullifies the given key field in the given RawObject --  rawAccess mode
     * is implied.
     */
    boolean nullifySecKey(Catalog catalog,
                          Object entity,
                          String keyName,
                          Object keyElement) {
        throw new UnsupportedOperationException(className);
    }

    /**
     * Returns whether the entity's primary key field is null or zero, as
     * defined for primary keys that are assigned from a sequence.
     */
    boolean isPriKeyNullOrZero(Object o, boolean rawAccess) {
        throw new UnsupportedOperationException(className);
    }

    /**
     * Gets the primary key field from the given object and writes it to the
     * given output data bytes.  This is a separate operation because the
     * primary key data bytes are stored separately from the rest of the
     * record.
     */
    void writePriKey(Object o, EntityOutput output, boolean rawAccess) {
        throw new UnsupportedOperationException(className);
    }

    /**
     * Reads the primary key from the given input bytes and sets the primary
     * key field in the given object.  This is complement of writePriKey().
     */
    void readPriKey(Object o, EntityInput input, boolean rawAccess) {
        throw new UnsupportedOperationException(className);
    }
}
