/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
 * 
 * This program and the accompanying materials are made available under
 * the terms of the Common Public License v1.0 which accompanies this distribution,
 * and is available at http://www.eclipse.org/legal/cpl-v10.html
 * 
 * $Id: InstrVisitor.java,v 1.1.1.1.2.4 2004/07/16 23:32:28 vlad_r Exp $
 */
package com.vladium.emma.instr;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import com.vladium.jcd.cls.*;
import com.vladium.jcd.cls.attribute.*;
import com.vladium.jcd.cls.constant.CONSTANT_Class_info;
import com.vladium.jcd.cls.constant.CONSTANT_Long_info;
import com.vladium.jcd.cls.constant.CONSTANT_Methodref_info;
import com.vladium.jcd.cls.constant.CONSTANT_String_info;
import com.vladium.jcd.compiler.CodeGen;
import com.vladium.jcd.lib.Types;
import com.vladium.jcd.opcodes.IOpcodes;
import com.vladium.logging.Logger;
import com.vladium.util.ByteArrayOStream;
import com.vladium.util.IConstants;
import com.vladium.util.IntIntMap;
import com.vladium.util.IntObjectMap;
import com.vladium.util.IntSet;
import com.vladium.util.asserts.$assert;
import com.vladium.emma.IAppConstants;
import com.vladium.emma.data.ClassDescriptor;
import com.vladium.emma.data.CoverageOptions;
import com.vladium.emma.data.IMetadataConstants;
import com.vladium.emma.data.MethodDescriptor;

// ----------------------------------------------------------------------------
/**
 * @author Vlad Roubtsov, (C) 2003
 */
public
final class InstrVisitor extends AbstractClassDefVisitor
                         implements IClassDefVisitor, IAttributeVisitor, IOpcodes, IConstants
{
    // public: ................................................................
    
    // TODO: m_instrument is unused

    public static final class InstrResult
    {
        public boolean m_instrumented;
        public ClassDescriptor m_descriptor;
        
    } // end of nested class    
    
    public InstrVisitor (final CoverageOptions options)
    {
        m_excludeSyntheticMethods = options.excludeSyntheticMethods ();
        m_excludeBridgeMethods = options.excludeBridgeMethods ();
        m_doSUIDCompensation = options.doSUIDCompensation ();
        
        m_log = Logger.getLogger ();
    }
    
    /**
     * Analyzes 'cls' and/or instruments it for coverage:
     * <ul>
     *  <li> if 'instrument' is true, the class definition is instrumented for
     *       coverage if that is feasible
     *  <li> if 'metadata' is true, the class definition is analysed
     *       to create a {@link ClassDescriptor} for the original class definition 
     * </ul>
     * This method returns null if 'metadata' is 'false' *or* if 'cls' is an
     * interface [the latter precludes coverage of interface static
     * initializers and may be removed in the future].<P>
     * 
     * NOTE: if 'instrument' is 'true', the caller should always assume that 'cls'
     * has been mutated by this method even if it returned null. The caller should
     * then revert to the original class definition that was created as a
     * <code>cls.clone()</code> or by retaining the original definition bytes.
     * This part of contract is for efficienty and also simplifies the implementation. 
     */
    public void process (final ClassDef cls,
                         final boolean ignoreAlreadyInstrumented,
                         final boolean instrument, final boolean metadata,
                         final InstrResult out)
    {
        out.m_instrumented = false;
        out.m_descriptor = null;
        
        if (! (instrument || metadata)) return; // nothing to do

        if (cls.isInterface ())
            return; // skip interfaces [may change in the future]
        else
        {
            reset ();
            
            m_cls = cls;
            
            // TODO: handle classes that cannot be instrumented due to bytecode/JVM limitations
            m_instrument = instrument;
            m_metadata = metadata;
            m_ignoreAlreadyInstrumented = ignoreAlreadyInstrumented;
            
            // TODO: create 'no instrumentation' execution path here
            
            visit ((ClassDef) null, null); // potentially changes m_instrument and m_metadata
            
            if (m_metadata)
            {
                setClassName (cls.getName ());
                
                out.m_descriptor = new ClassDescriptor (m_classPackageName, m_className, m_classSignature, m_classSrcFileName, m_classMethodDescriptors);
            }
            
            out.m_instrumented = m_instrument;
        }
    }
    

    // IClassDefVisitor:
    
    public Object visit (final ClassDef ignore, final Object ctx)
    {
        final ClassDef cls = m_cls;
        final String clsVMName = cls.getName ();
        final String clsName = Types.vmNameToJavaName (clsVMName);
        
        final boolean trace1 = m_log.atTRACE1 (); 
        if (trace1) m_log.trace1 ("visit", "class: [" + clsVMName + "]");
        
        
        // skip synthetic classes if enabled:
        if (SKIP_SYNTHETIC_CLASSES && cls.isSynthetic ())
        {
            m_instrument = false;
            m_metadata = false;
            
            if (trace1) m_log.trace1 ("visit", "skipping synthetic class");
            return ctx;
        }
        
        // TODO: ideally, this check should be done in outer scope somewhere
        if (! m_warningIssued && clsName.startsWith (IAppConstants.APP_PACKAGE))
        {
            m_warningIssued = true;
            
            m_log.warning (IAppConstants.APP_NAME + " classes appear to be included on the instrumentation");
            m_log.warning ("path: this is not a correct way to use " + IAppConstants.APP_NAME);
        }
        
        // field uniqueness check done to detect double instrumentation:
        {
            final int [] existing = cls.getFields (COVERAGE_FIELD_NAME);
            if (existing.length > 0)
            {
                m_instrument = false;
                m_metadata = false;
                
                if (m_ignoreAlreadyInstrumented)
                {
                    if (trace1) m_log.trace1 ("visit", "skipping instrumented class");
                    return ctx;
                }
                else
                {
                    // TODO: use a app coded exception
                    throw new IllegalStateException ("class [" + clsName + "] appears to be instrumented already");
                }
            }
        }
        
        final IConstantCollection constants = cls.getConstants ();
        
        SyntheticAttribute_info syntheticMarker = null;
        
        // cache the location of "Synthetic" string:
        {
            if (MARK_ADDED_ELEMENTS_SYNTHETIC)
                m_syntheticStringIndex = cls.addCONSTANT_Utf8 (Attribute_info.ATTRIBUTE_SYNTHETIC, true);
        }
                
        // add a Fieldref for the runtime coverage collector field:
        {
            // note: this is a bit premature if the class has no methods that need
            // instrumentation
            // TODO: the mutated version is easily discardable; however, this case
            // needs attention at metadata/report generation level
            
            final int coverageFieldOffset;
            final String fieldDescriptor = "[[Z";
            
            // note that post-4019 builds can modify this field outside of <clinit> (although
            // it can only happen as part of initializing a set of classes); however, it is legal
            // to declare this field final:
            
            final int fieldModifiers = IAccessFlags.ACC_PRIVATE | IAccessFlags.ACC_STATIC | IAccessFlags.ACC_FINAL;
            
            // add declared field:
            if (MARK_ADDED_ELEMENTS_SYNTHETIC)
            {
                final IAttributeCollection fieldAttributes = ElementFactory.newAttributeCollection (1);

                syntheticMarker = new SyntheticAttribute_info (m_syntheticStringIndex);
                fieldAttributes.add (syntheticMarker);
    
                coverageFieldOffset = cls.addField (COVERAGE_FIELD_NAME, fieldDescriptor,
                    fieldModifiers, fieldAttributes);
            }
            else
            {
                coverageFieldOffset = cls.addField (COVERAGE_FIELD_NAME, fieldDescriptor,
                    fieldModifiers);
            }
            
            //add fieldref:
            m_coverageFieldrefIndex = cls.addFieldref (coverageFieldOffset);
        }
        
        // add a Methodref for Runtime.r():
        {
            // TODO: compute this without loading Runtime Class?
            final String classJVMName = "com/vladium/emma/rt/RT";
            final int class_index = cls.addClassref (classJVMName);
            
            // NOTE: keep this descriptor in sync with the actual signature
            final String methodDescriptor = "([[ZLjava/lang/String;J)V";
            final int nametype_index = cls.addNameType ("r", methodDescriptor);
            
            m_registerMethodrefIndex = constants.add (new CONSTANT_Methodref_info (class_index, nametype_index));
        }
        
        // SF FR 971186: split the init logic into a separate method so it could
        // be called from regular method headers if necessary: 
        
        // add a Methodref for pre-<clinit> method:
        {
            // NOTE: keep this descriptor in sync with the actual signature
            final String methodDescriptor = "()[[Z";
            final int nametype_index = cls.addNameType (PRECLINIT_METHOD_NAME, methodDescriptor);
            
            m_preclinitMethodrefIndex = constants.add (new CONSTANT_Methodref_info (cls.getThisClassIndex (), nametype_index));
        }
        
        // add a CONSTANT_String that corresponds to the class name [in JVM format]:
        {
            m_classNameConstantIndex = constants.add (new CONSTANT_String_info (cls.getThisClass ().m_name_index));
        }
        
        // visit method collection:         
        visit (cls.getMethods (), ctx);
        
        // if necessary, do SUID compensation [need to be done after method
        // visits when it is known whether a <clinit> was added]:
        if (m_doSUIDCompensation)
        {
            // compensation not necessary if the original clsdef already defined <clinit>:
            boolean compensate = ((m_clinitStatus & IMetadataConstants.METHOD_ADDED) != 0);
            
            int existingSUIDFieldCount = 0;
            
            if (compensate)
            {
                // compensation not necessary if the original clsdef already controlled it via 'serialVersionUID':
                {
                    final int [] existing = cls.getFields (SUID_FIELD_NAME);
                    existingSUIDFieldCount = existing.length;
                    
                    if (existingSUIDFieldCount > 0)
                    {
                        final IFieldCollection fields = cls.getFields ();
                        
                        for (int f = 0; f < existingSUIDFieldCount; ++ f)
                        {
                            final Field_info field = fields.get (existing [f]);
                            if ((field.getAccessFlags () & (IAccessFlags.ACC_STATIC | IAccessFlags.ACC_FINAL))
                                 == (IAccessFlags.ACC_STATIC | IAccessFlags.ACC_FINAL))
                            {
                                // TODO: should also check for presence of a non-zero initializer
                                
                                compensate = false;
                                break;
                            }
                        }
                    }
                }
                
                // compensation not necessary if we can determine that this class
                // does not implement java.io.Serializable/Externalizable:
                
                if (compensate && (cls.getThisClassIndex () == 0)) // no superclasses [this tool can't traverse inheritance chains]
                {
                    boolean serializable = false;
                    
                    final IInterfaceCollection interfaces = cls.getInterfaces ();
                    for (int i = 0, iLimit = interfaces.size (); i < iLimit; ++ i)
                    {
                        final CONSTANT_Class_info ifc = (CONSTANT_Class_info) constants.get (interfaces.get (i));
                        final String ifcName = ifc.getName (cls); 
                        if (JAVA_IO_SERIALIZABLE_NAME.equals (ifcName) || JAVA_IO_EXTERNALIZABLE_NAME.equals (ifcName))
                        {
                            serializable = true;
                            break;
                        }
                    }
                    
                    if (! serializable) compensate = false;
                }
            }
            
            if (compensate)
            {
                if (existingSUIDFieldCount > 0)
                {
                    // if we get here, the class declares a 'serialVersionUID' field
                    // that is not both static and final and/or is not initialized
                    // statically: warn that SUID compensation may not work
                    
                    m_log.warning ("class [" + clsName + "] declares a 'serialVersionUID'");
                    m_log.warning ("field that is not static and final: this is likely an implementation mistake");
                    m_log.warning ("and can interfere with " + IAppConstants.APP_NAME + "'s SUID compensation");
                }
                
                final String fieldDescriptor = "J";
                final int fieldModifiers = IAccessFlags.ACC_PRIVATE | IAccessFlags.ACC_STATIC | IAccessFlags.ACC_FINAL;
                final IAttributeCollection fieldAttributes = ElementFactory.newAttributeCollection (MARK_ADDED_ELEMENTS_SYNTHETIC ? 2 : 1);
    
                final int nameIndex = cls.addCONSTANT_Utf8 (Attribute_info.ATTRIBUTE_CONSTANT_VALUE, true);
                final int valueIndex = constants.add (new CONSTANT_Long_info (cls.computeSUID (true))); // ignore the added <clinit>
                
                final ConstantValueAttribute_info initializer = new ConstantValueAttribute_info (nameIndex, valueIndex);
                fieldAttributes.add (initializer);
                    
                if (MARK_ADDED_ELEMENTS_SYNTHETIC)
                {
                    if (syntheticMarker == null) syntheticMarker = new SyntheticAttribute_info (m_syntheticStringIndex);
                    fieldAttributes.add (syntheticMarker);
                }
                
                cls.addField (SUID_FIELD_NAME, fieldDescriptor, fieldModifiers, fieldAttributes);
            }
            
        } // if (m_doSUIDCompensation)
        
        // visit class attributes [to get src file name, etc]:
        visit (cls.getAttributes (), ctx);
        
        return ctx;
    }

    
    public Object visit (final IMethodCollection methods, final Object ctx)
    {
        final ClassDef cls = m_cls;
        
        final boolean trace2 = m_log.atTRACE2 ();
        
        final int originalMethodCount = methods.size ();
        final boolean constructMetadata = m_metadata;
        
        // create block count map: TODO: is the extra slot really needed?
        // - create [potentially unused] slot for added <clinit>
        m_classBlockCounts = new int [originalMethodCount + 1];        
        
        if (constructMetadata)
        {
            // prepare to collect metadata:
            m_classBlockMetadata = new int [originalMethodCount + 1] [] []; // same comments as above
            
            m_classMethodDescriptors = new MethodDescriptor [originalMethodCount];
        }
        
       
        // visit each original method:
        
        for (int m = 0; m < originalMethodCount; ++ m)
        {
            final Method_info method = methods.get (m);
            m_methodName = method.getName (cls); 
            if (trace2) m_log.trace2 ("visit", (method.isSynthetic () ? "synthetic " : "") + "method #" + m + ": [" + m_methodName + "]");
            
            final boolean isClinit = IClassDefConstants.CLINIT_NAME.equals (m_methodName);
                        
            // TODO: research whether synthetic methods add nontrivially to line coverage or not
            
            boolean excluded = false;
            
            if (! isClinit)
            {
                if (m_excludeSyntheticMethods && method.isSynthetic ())
                {
                    excluded = true;
                    if (trace2) m_log.trace2 ("visit", "skipped synthetic method");
                }
                else if (m_excludeBridgeMethods && method.isBridge ())
                {
                    excluded = true;
                    if (trace2) m_log.trace2 ("visit", "skipped bridge method");
                } 
            }
            
            if (excluded)
            {
                if (constructMetadata)
                {
                    m_classMethodDescriptors [m] = new MethodDescriptor (m_methodName, method.getDescriptor (cls), IMetadataConstants.METHOD_EXCLUDED, m_methodBlockSizes, null, 0);
                }
            }
            else
            {
                if ((method.getAccessFlags () & (IAccessFlags.ACC_ABSTRACT | IAccessFlags.ACC_NATIVE)) != 0)
                {
                    if (constructMetadata)
                    {
                        m_classMethodDescriptors [m] = new MethodDescriptor (m_methodName, method.getDescriptor (cls), IMetadataConstants.METHOD_ABSTRACT_OR_NATIVE, m_methodBlockSizes, null, 0);
                    }
                    
                    if (trace2) m_log.trace2 ("visit", "skipped " + (method.isAbstract () ? "abstract" : "native") + " method");
                }
                else // this is a regular, non-<clinit> method that has bytecode:
                {
                    // reset first line:
                    m_methodFirstLine = 0;
                    
                    // set current method ID:
                    m_methodID = m;
                    
                    if (isClinit)
                    {
                        // if <clinit> found: note the ID but delay processing until the very end
                        m_clinitID = m;
                        if (trace2) m_log.trace2 ("visit", "<clinit> method delayed");
                    }
                    else
                    {
                        // visit attributes [skip visit (IAttributeCollection) method]:    
                        final IAttributeCollection attributes = method.getAttributes ();
                        final int attributeCount = attributes.size ();
                        for (int a = 0; a < attributeCount; ++ a)
                        {
                            final Attribute_info attribute = attributes.get (a);
                            attribute.accept (this, ctx);
                        }
                        
                        if (constructMetadata)
                        {
                            if ($assert.ENABLED) $assert.ASSERT (m_classBlockCounts [m_methodID] > 0, "invalid block count for method " + m_methodID + ": " + m_classBlockCounts [m_methodID]);
                            if ($assert.ENABLED) $assert.ASSERT (m_methodBlockSizes != null && m_methodBlockSizes.length == m_classBlockCounts [m_methodID], "invalid block sizes map for method " + m_methodID);
                            
                            final int [][] methodBlockMetadata = m_classBlockMetadata [m_methodID];
                            final int status = (methodBlockMetadata == null ? IMetadataConstants.METHOD_NO_LINE_NUMBER_TABLE : 0);
                            
                            m_classMethodDescriptors [m] = new MethodDescriptor (m_methodName, method.getDescriptor (cls), status, m_methodBlockSizes, methodBlockMetadata, m_methodFirstLine);
                        }
                    }                
                }
            }
        }
        
        // add <clinit> (and instrument if needed) [a <clinit> is always needed
        // even if there are no other instrumented method to act as a load hook]:
        
        final boolean instrumentClinit = false; // TODO: make use of this [to limit instrumentation to clinitHeader only], take into account whether we added and whether it is synthetic
        final Method_info clinit;
        
        if (m_clinitID >= 0)
        {
            // <clinit> existed in the original class: needs to be covered
            
            // m_clinitStatus = 0;
            clinit = methods.get (m_clinitID);
            
            m_classInstrMethodCount = originalMethodCount;
        }
        else
        {
            // there is no <clinit> defined by the original class: add one [and mark it synthetic]
            
            m_clinitStatus = IMetadataConstants.METHOD_ADDED;  // mark as added by us
            
            final int attribute_name_index = cls.addCONSTANT_Utf8 (Attribute_info.ATTRIBUTE_CODE, true);
            final int name_index = cls.addCONSTANT_Utf8 (IClassDefConstants.CLINIT_NAME, true);
            final int descriptor_index = cls.addCONSTANT_Utf8 ("()V", true);
            
            final IAttributeCollection attributes;
            
            if (MARK_ADDED_ELEMENTS_SYNTHETIC)
                attributes = ElementFactory.newAttributeCollection (2);
            else
                attributes = ElementFactory.newAttributeCollection (1);
            
            final CodeAttribute_info code = new CodeAttribute_info (attribute_name_index,
                0, 0,
                new byte [] {(byte) _return},
                AttributeElementFactory.newExceptionHandlerTable (0),
                ElementFactory.newAttributeCollection (0));
                
            attributes.add (code);
            
            if (MARK_ADDED_ELEMENTS_SYNTHETIC)
            {
                attributes.add (new SyntheticAttribute_info (m_syntheticStringIndex));
            }
            
            clinit = new Method_info (IAccessFlags.ACC_STATIC | IAccessFlags.ACC_PRIVATE, name_index, descriptor_index, attributes);
            
            m_clinitID = cls.addMethod (clinit);
            
            if (trace2) m_log.trace2 ("visit", "added synthetic <clinit> method");
            
            // TODO: this should exclude <clinit> if it were added by us
            m_classInstrMethodCount = originalMethodCount + 1;
        }
        
        if ($assert.ENABLED) $assert.ASSERT (m_classInstrMethodCount >= 0,
            "m_classInstrMethodCount not set");
        

        // visit <clinit>:
        {
            m_methodFirstLine = 0;
            m_methodID = m_clinitID;
            
            if (trace2) m_log.trace2 ("visit", (clinit.isSynthetic () ? "synthetic " : "") + "method #" + m_methodID + ": [<clinit>]");
            
            final IAttributeCollection attributes = clinit.getAttributes ();
            final int attributeCount = attributes.size ();
            for (int a = 0; a < attributeCount; ++ a)
            {
                final Attribute_info attribute = attributes.get (a);
                attribute.accept (this, ctx);
            }
        }

        // add pre-<clinit> method:
        
        {
            final int attribute_name_index = cls.addCONSTANT_Utf8 (Attribute_info.ATTRIBUTE_CODE, true);
            final int name_index = cls.addCONSTANT_Utf8 (PRECLINIT_METHOD_NAME, false);
            final int descriptor_index = cls.addCONSTANT_Utf8 ("()[[Z", false);
            
            final IAttributeCollection attributes;
            
            if (MARK_ADDED_ELEMENTS_SYNTHETIC)
                attributes = ElementFactory.newAttributeCollection (2);
            else
                attributes = ElementFactory.newAttributeCollection (1);
            
            final ByteArrayOStream buf = new ByteArrayOStream (PRECLINIT_INIT_CAPACITY);  
            {
                final int [] blockCounts = m_classBlockCounts;
                final int instrMethodCount = m_classInstrMethodCount; // actual number of methods to instrument may be less than the size of the block map 

                if ($assert.ENABLED) $assert.ASSERT (blockCounts != null && blockCounts.length >= instrMethodCount,
                    "invalid block count map");
                
                // new and set COVERAGE_FIELD:
                
                // push first dimension:
                CodeGen.push_int_value (buf, cls, instrMethodCount);
                
                // [stack +1]
                
                // new boolean [][]:
                final int type_index = cls.addClassref ("[[Z");
                buf.write4 (_multianewarray,
                            type_index >>> 8,    // indexbyte1
                            type_index,          // indexbyte2
                            1); // only one dimension created here
                
                // [stack +1]
                
                // clone array ref:
                buf.write4 (_dup,
                
                // [stack +2]
                
                // store in the static field
                            _putstatic,
                            m_coverageFieldrefIndex >>> 8,    // indexbyte1
                            m_coverageFieldrefIndex);          // indexbyte2
                
                // [stack +1]
                
                for (int m = 0; m < instrMethodCount; ++ m)
                {
                    final int blockCount = blockCounts [m]; 
                    if (blockCount > 0)
                    {
                        // clone array ref:
                        buf.write (_dup);
                        
                        // [stack +2]
                        
                        // push outer dim index:
                        CodeGen.push_int_value (buf, cls, m);
                        
                        // [stack +3]
                        
                        // push dim:
                        CodeGen.push_int_value (buf, cls, blockCount);
                        
                        // [stack +4]
                        
                        // newarray boolean []:
                        buf.write3 (_newarray,
                                    4, // "T_BOOLEAN"
                        
                        // add subarray to the outer array:
                                    _aastore);
                        
                        // [stack +1]
                    }
                }
                
                // [stack +1]
                
                {
                    // clone array ref
                    buf.write (_dup);
                    
                    // [stack +2]
                    
                    CodeGen.push_constant_index (buf, m_classNameConstantIndex);
                    
                    // [stack +3]

                    buf.write3 (_ldc2_w,
                                m_stampIndex >>> 8,    // indexbyte1
                                m_stampIndex);         // indexbyte2
                    
                    // [stack +5]
                    
                    buf.write3 (_invokestatic,
                                m_registerMethodrefIndex >>> 8,    // indexbyte1
                                m_registerMethodrefIndex);         // indexbyte2
                    
                    // [stack +1]
                }
                
                // pop and return extra array ref:
                buf.write (_areturn);
                
                // [stack +0]
            }

            final CodeAttribute_info code = new CodeAttribute_info (attribute_name_index,
                5, 0, // adjust constants if the bytecode emitted above changes
                EMPTY_BYTE_ARRAY,
                AttributeElementFactory.newExceptionHandlerTable (0),
                ElementFactory.newAttributeCollection (0));
            
            code.setCode (buf.getByteArray (), buf.size ());
                
            attributes.add (code);
            
            if (MARK_ADDED_ELEMENTS_SYNTHETIC)
            {
                attributes.add (new SyntheticAttribute_info (m_syntheticStringIndex));
            }
            
            final Method_info preclinit = new Method_info (IAccessFlags.ACC_STATIC | IAccessFlags.ACC_PRIVATE, name_index, descriptor_index, attributes);
            cls.addMethod (preclinit);
            
            if (trace2) m_log.trace2 ("visit", "added synthetic pre-<clinit> method");
        }

        
        if (constructMetadata)
        {
            if ($assert.ENABLED) $assert.ASSERT (m_classBlockCounts [m_methodID] > 0, "invalid block count for method " + m_methodID + " (" + IClassDefConstants.CLINIT_NAME + "): " + m_classBlockCounts [m_methodID]);
            if ($assert.ENABLED) $assert.ASSERT (m_methodBlockSizes != null && m_methodBlockSizes.length == m_classBlockCounts [m_methodID], "invalid block sizes map for method " + m_methodID);
            
            final int [][] methodBlockMetadata = m_classBlockMetadata [m_methodID];
            m_clinitStatus |= (methodBlockMetadata == null ? IMetadataConstants.METHOD_NO_LINE_NUMBER_TABLE : 0);
            
            // TODO: this still does not process not added/synthetic case  
            
            if ((m_clinitStatus & IMetadataConstants.METHOD_ADDED) == 0)
                m_classMethodDescriptors [m_methodID] = new MethodDescriptor (IClassDefConstants.CLINIT_NAME, clinit.getDescriptor (cls), m_clinitStatus, m_methodBlockSizes, methodBlockMetadata, m_methodFirstLine);
        }
        
        return ctx;
    }


    public Object visit (final IAttributeCollection attributes, Object ctx)
    {
        for (int a = 0, aCount = attributes.size (); a < aCount; ++ a)
        {
            // TODO: define a global way to set the mask set of attrs to be visited
            attributes.get (a).accept (this, ctx);
        } 

        return ctx;
    }
    
    
    // IAttributeVisitor:

    public Object visit (final CodeAttribute_info attribute, final Object ctx)
    {
        final boolean trace2 = m_log.atTRACE2 ();
        final boolean trace3 = m_log.atTRACE3 ();
        
        final byte [] code = attribute.getCode ();
        final int codeSize = attribute.getCodeSize ();
        
        if (trace2) m_log.trace2 ("visit", "code attribute for method #" + m_methodID + ": size = " + codeSize);
        
        final IntSet leaders = new IntSet ();
        
        // instructionMap.get(ip) is the number of instructions in code[0-ip)
        // [this map will include a mapping for code length as well]
        final IntIntMap /* int(ip)->instr count */ instructionMap = new IntIntMap ();
        
        // add first instruction and all exc handler start pcs:
        leaders.add (0); 
        
        final IExceptionHandlerTable exceptions = attribute.getExceptionTable ();
        final int exceptionCount = exceptions.size ();
        for (int e = 0; e < exceptionCount; ++ e)
        {
            final Exception_info exception = exceptions.get (e);
            leaders.add (exception.m_handler_pc);
        }
        
        
        final IntObjectMap branches = new IntObjectMap ();
        
        // determine block leaders [an O(code length) loop]:
        
        boolean branch = false;
        boolean wide = false;

        int instructionCount = 0;
        instructionMap.put (0, 0);
        
        for (int ip = 0; ip < codeSize; )
        {
            final int opcode = 0xFF & code [ip];
            int size = 0; // will be set to -<real size> for special cases in the switch below 
            
            //if (trace3) m_log.trace3 ("parse", MNEMONICS [opcode]);
            // "visitor.visit (opcode, wide, ip, null)":
            
            { // "opcode visit" logic:
                
                int iv, ov;
                
                if (branch)
                {
                    // previous instruction was a branch: this one is a leader
                    leaders.add (ip);
                    branch = false;
                }
                
                switch (opcode)
                {
                    case _ifeq:
                    case _iflt:
                    case _ifle:
                    case _ifne:
                    case _ifgt:
                    case _ifge:
                    case _ifnull:
                    case _ifnonnull:
                    case _if_icmpeq:
                    case _if_icmpne:
                    case _if_icmplt:
                    case _if_icmpgt:
                    case _if_icmple:
                    case _if_icmpge:
                    case _if_acmpeq:
                    case _if_acmpne:
                    {
                        //ov = getI2 (code, ip + 1);
                        int scan = ip + 1;
                        ov = (code [scan] << 8) | (0xFF & code [++ scan]);
                        
                        final int target = ip + ov;
                        leaders.add (target); 
                        
                        branches.put (ip, new IFJUMP2 (opcode, target));
                        branch = true;
                    }
                    break;


                    case _goto:
                    case _jsr:
                    {
                        //ov = getI2 (code, ip + 1);
                        int scan = ip + 1;
                        ov = (code [scan] << 8) | (0xFF & code [++ scan]);
                        
                        final int target = ip + ov;
                        leaders.add (target); 
                        
                        branches.put (ip, new JUMP2 (opcode, target));
                        branch = true;
                    }
                    break;


                    case _lookupswitch:
                    {
                        int scan = ip + 4 - (ip & 3); // eat padding
                        
                        ov = (code [scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                        leaders.add (ip + ov);
                        
                        //final int npairs = getU4 (code, scan);
                        //scan += 4;
                        final int npairs = ((0xFF & code [++ scan]) << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                        
                        final int [] keys = new int [npairs];
                        final int [] targets = new int [npairs + 1];
                        targets [0] = ip + ov;
                        
                        for (int p = 0; p < npairs; ++ p)
                        {
                            //iv = getI4 (code, scan);
                            //scan += 4;
                            iv = (code [++ scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                            keys [p] = iv;
                            
                            
                            //ov = getI4 (code, scan);
                            //scan += 4;
                            ov = (code [++ scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                            targets [p + 1] = ip + ov;
                            leaders.add (ip + ov);
                        }
                        
                        branches.put (ip, new LOOKUPSWITCH (keys, targets));
                        branch = true;
                        
                        size = ip - scan - 1; // special case
                    }
                    break;

                    
                    case _tableswitch:
                    {
                        int scan = ip + 4 - (ip & 3); // eat padding
                        
                        ov = (code [scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                        leaders.add (ip + ov);
                                                
                        //final int low = getI4 (code, scan + 4);
                        final int low = (code [++ scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                        //final int high = getI4 (code, scan + 8);
                        //scan += 12;
                        final int high = (code [++ scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                        
                        final int [] targets = new int [high - low + 2];
                        targets [0] = ip + ov;
                        
                        for (int index = low; index <= high; ++ index)
                        {
                            //ov = getI4 (code, scan);
                            ov = (code [++ scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                            targets [index - low + 1] = ip + ov;
                            leaders.add (ip + ov);
                            //scan += 4;
                        }

                        branches.put (ip, new TABLESWITCH (low, high, targets));
                        branch = true;
                        
                        size = ip - scan - 1; // special case
                    }
                    break;
                        

                    case _goto_w:
                    case _jsr_w:
                    {
                        int scan = ip + 1;
                        //ov = getI4 (code, ip + 1);
                        ov = (code [scan] << 24) | ((0xFF & code [++ scan]) << 16) | ((0xFF & code [++ scan]) << 8) | (0xFF & code [++ scan]);
                        final int target = ip + ov;
                        
                        leaders.add (target);
                        
                        branches.put (ip, new JUMP4 (opcode, target));
                        branch = true;
                    }
                    break;


                    case _ret:
                    {
                        int scan = ip + 1;
                        iv = wide ? (((0xFF & code [scan]) << 8) | (0xFF & code [++ scan])) : (0xFF & code [scan]);
                        
                        branches.put (ip, new RET (opcode, iv));
                        branch = true;
                    } 
                    break; 


                    case _athrow:
                    case _ireturn:
                    case _lreturn:
                    case _freturn:
                    case _dreturn:
                    case _areturn:
                    case _return:
                    {
                        branches.put (ip, new TERMINATE (opcode));
                        branch = true;
                    }
                    break;
                    
                } // end of switch
                
            } // end of processing the current opcode
            
            
            // shift to the next instruction [this is the only block that adjusts 'ip']:
            
            if (size == 0)
                size = (wide ? WIDE_SIZE : NARROW_SIZE) [opcode];
            else
                size = -size;
            
            ip += size;
            wide = (opcode == _wide);
            
            instructionMap.put (ip, ++ instructionCount);
            
        } // end of for
        
        
        // split 'code' into an ordered list of basic blocks [O(block count) loops]:
        
        final int blockCount = leaders.size ();
        if (trace2) m_log.trace2 ("visit", "method contains " + blockCount + " basic blocks");
        
        final BlockList blocks = new BlockList (blockCount);
        
        final int [] _leaders = new int [blockCount + 1]; // room for end-of-code leader at the end 
        leaders.values (_leaders, 0);
        _leaders [blockCount] = codeSize;
        
        Arrays.sort (_leaders);
        
        final int [] _branch_locations = branches.keys (); 
        Arrays.sort (_branch_locations);
        
        final IntIntMap leaderToBlockID = new IntIntMap (_leaders.length);
        
        if (m_metadata)
        {
            // help construct a MethodDescriptor for the current method:
            
            m_methodBlockSizes = new int [blockCount];
            m_methodBlockOffsets = _leaders;
        }

        // compute signature even if metadata is not needed (because the instrumented
        // classdef uses it):
        consumeSignatureData (m_methodID, _leaders);
        
        // pass 1:
        
        final int [] intHolder = new int [1];
        int instr_count = 0, prev_instr_count;
        
        for (int bl = 0, br = 0; bl < blockCount; ++ bl)
        {
            final Block block = new Block ();
            blocks.m_blocks.add (block);
            
            final int leader = _leaders [bl];
            
            block.m_first = leader; // m_first set
            leaderToBlockID.put (leader, bl);
            
            final int next_leader = _leaders [bl + 1];
            boolean branchDelimited = false;
            
            prev_instr_count = instr_count;

            if (_branch_locations.length > br)
            {
                final int next_branch_location = _branch_locations [br];
                if (next_branch_location < next_leader)
                {
                    branchDelimited = true;
                    
                    block.m_length = next_branch_location - leader; // m_length set
                    
                    if ($assert.ENABLED)
                        $assert.ASSERT (instructionMap.get (next_branch_location, intHolder), "no mapping for " + next_branch_location);
                    else
                        instructionMap.get (next_branch_location, intHolder);
                        
                    instr_count = intHolder [0] + 1; // [+ 1 for the branch]
                     
                    block.m_branch = (Branch) branches.get (next_branch_location);
                    block.m_branch.m_parentBlockID = bl; // m_branch set
                    
                    ++ br;
                }
            }
            
            if (! branchDelimited)
            {
                block.m_length = next_leader - leader; // m_length set
                
                if ($assert.ENABLED)
                    $assert.ASSERT (instructionMap.get (next_leader, intHolder), "no mapping for " + next_leader);
                else
                    instructionMap.get (next_leader, intHolder);
                
                instr_count = intHolder [0];
            }
            
            block.m_instrCount = instr_count - prev_instr_count; // m_instrCount set
            
            if ($assert.ENABLED) $assert.ASSERT (block.m_length == 0 || block.m_instrCount > 0, "invalid instr count for block " + bl + ": " + block.m_instrCount);
            if (m_metadata) m_methodBlockSizes [bl] = block.m_instrCount; 
        }
        
        // pass 2:
        
        final Block [] _blocks = (Block []) blocks.m_blocks.toArray (new Block [blockCount]);
        
        for (int l = 0; l < blockCount; ++ l)
        {
            final Block block = _blocks [l];
             
            if (block.m_branch != null)
            {
                final int [] targets = block.m_branch.m_targets;
                if (targets != null)
                {
                    for (int t = 0, targetCount = targets.length; t < targetCount; ++ t)
                    {
                        // TODO: HACK ! convert block absolute offsets to block IDs:
                        
                        if ($assert.ENABLED)
                            $assert.ASSERT (leaderToBlockID.get (targets [t], intHolder), "no mapping for " + targets [t]);
                        else
                            leaderToBlockID.get (targets [t], intHolder);
                            
                        targets [t] = intHolder [0];
                    }
                }
            }
        }

        
        // update block count map [used later by <clinit> visit]:
        m_classBlockCounts [m_methodID] = blockCount;
        
        // actual basic block instrumentation:
        {
            if (trace2) m_log.trace2 ("visit", "instrumenting... ");
            
            // determine the local var index for the var that will alias COVERAGE_FIELD:
            final int localVarIndex = attribute.m_max_locals ++;
            
            if (m_methodID == m_clinitID) // note: m_clinitID can be -1 if <clinit> has not been visited yet
            {
                 // add a long stamp constant after all the original methods have been visited:
             
                m_stampIndex = m_cls.getConstants ().add (new CONSTANT_Long_info (m_classSignature));
                
                blocks.m_header = new clinitHeader (this, localVarIndex);
            }
            else
                blocks.m_header = new methodHeader (this, localVarIndex);
            
            int headerMaxStack = blocks.m_header.maxstack ();
            int methodMaxStack = 0;
            
            for (int l = 0; l < blockCount; ++ l)
            {
                final Block block = _blocks [l];
                
                final CodeSegment insertion = new BlockSegment (this, localVarIndex, l);
                block.m_insertion = insertion;
                
                final int insertionMaxStack = insertion.maxstack (); 
                if (insertionMaxStack > methodMaxStack)
                    methodMaxStack = insertionMaxStack;
            }
            
            // update maxstack as needed [it can only grow]:
            {
                final int oldMaxStack = attribute.m_max_stack;
                
                attribute.m_max_stack += methodMaxStack; // this is not precise, but still need to add because the insertion may be happening at the old maxstack point
                
                if (headerMaxStack > attribute.m_max_stack)
                attribute.m_max_stack = headerMaxStack;
                
                if (trace3) m_log.trace3 ("visit", "increasing maxstack by " + (attribute.m_max_stack - oldMaxStack));
            }
            
            if ($assert.ENABLED) $assert.ASSERT (blocks.m_header != null, "header not set");
        }
        

        // assemble all blocks into an instrumented code block:
        if (trace2) m_log.trace2 ("visit", "assembling... ");
        
        int newcodeCapacity = codeSize << 1;
        if (newcodeCapacity < EMIT_CTX_MIN_INIT_CAPACITY) newcodeCapacity = EMIT_CTX_MIN_INIT_CAPACITY;

        final ByteArrayOStream newcode = new ByteArrayOStream (newcodeCapacity); // TODO: empirical capacity
        final EmitCtx emitctx = new EmitCtx (blocks, newcode);
        
        // create a jump adjustment map:
        final int [] jumpAdjOffsets = new int [blockCount]; // room for initial 0  + (blockCount - 1)
        final int [] jumpAdjMap = new int [jumpAdjOffsets.length]; // room for initial 0  + (blockCount - 1)
        
        if ($assert.ENABLED) $assert.ASSERT (jumpAdjOffsets.length == jumpAdjMap.length,
            "jumpAdjOffsets and jumpAdjMap length mismatch");
        
        // header:
        blocks.m_header.emit (emitctx);
        // jumpAdjOffsets [0] = 0: redundant
        jumpAdjMap [0] = emitctx.m_out.size ();
        
        // rest of blocks:
        for (int l = 0; l < blockCount; ++ l)
        {
            final Block block = _blocks [l];
            
            if (l + 1 < blockCount)
            {
                jumpAdjOffsets [l + 1] = _blocks [l].m_first + _blocks [l].m_length; // implies the insertion goes just before the branch
            }
            
            block.emit (emitctx, code);
            
            // TODO: this breaks if code can shrink:
            if (l + 1 < blockCount)
            {
                jumpAdjMap [l + 1] = emitctx.m_out.size () - _blocks [l + 1].m_first;
            }
        }
        
        m_methodJumpAdjOffsets = jumpAdjOffsets;
        m_methodJumpAdjValues = jumpAdjMap;
        
        if (trace3)
        {
            final StringBuffer s = new StringBuffer ("jump adjustment map:" + EOL);
            for (int a = 0; a < jumpAdjOffsets.length; ++ a)
            {
                s.append ("    " + jumpAdjOffsets [a] + ": +" + jumpAdjMap [a]);
                if (a < jumpAdjOffsets.length - 1) s.append (EOL);
            }
            
            m_log.trace3 ("visit", s.toString ());
        }
        
        final byte [] _newcode = newcode.getByteArray (); // note: not cloned 
        final int _newcodeSize = newcode.size ();
         
        // [all blocks have had their m_first adjusted]
        
        // backpatching pass:        
        if (trace3) m_log.trace3 ("visit", "backpatching " + emitctx.m_backpatchQueue.size () + " ip(s)");
        
        for (Iterator i = emitctx.m_backpatchQueue.iterator (); i.hasNext (); )
        {
            final int [] patchData = (int []) i.next ();
            int ip = patchData [1];
            
            if ($assert.ENABLED) $assert.ASSERT (patchData != null, "null patch data for ip " + ip);
            
            final int jump = _blocks [patchData [3]].m_first - patchData [2];
            if ($assert.ENABLED) $assert.ASSERT (jump > 0, "negative backpatch jump offset " + jump + " for ip " + ip);
            
            switch (patchData [0])
            {
                case 4:
                {
                    _newcode [ip ++] = (byte) (jump >>> 24);
                    _newcode [ip ++] = (byte) (jump >>> 16);
                    
                } // *FALL THROUGH*
                
                case 2:
                {
                    _newcode [ip ++] = (byte) (jump >>> 8);
                    _newcode [ip] = (byte) jump;
                }
            }
        }
        
        attribute.setCode (_newcode, _newcodeSize);
        if (trace2) m_log.trace2 ("visit", "method assembled into " + _newcodeSize + " code bytes");

        
        // adjust bytecode offsets in the exception table:
        final IExceptionHandlerTable exceptionTable = attribute.getExceptionTable ();
        for (int e = 0; e < exceptionTable.size (); ++ e)
        {
            final Exception_info exception = exceptionTable.get (e);
            
            int adjSegment = lowbound (jumpAdjOffsets, exception.m_start_pc);
            exception.m_start_pc += jumpAdjMap [adjSegment];
            
            adjSegment = lowbound (jumpAdjOffsets, exception.m_end_pc);
            exception.m_end_pc += jumpAdjMap [adjSegment];
            
            adjSegment = lowbound (jumpAdjOffsets, exception.m_handler_pc);
            exception.m_handler_pc += jumpAdjMap [adjSegment];
        }

        
        // visit other nested attributes [LineNumberAttribute, etc]:    
        final IAttributeCollection attributes = attribute.getAttributes ();
        final int attributeCount = attributes.size ();
        for (int a = 0; a < attributeCount; ++ a)
        {
            final Attribute_info nested = attributes.get (a);
            nested.accept (this, ctx);
        }
        
        return ctx;
    }
    

    public Object visit (final LineNumberTableAttribute_info attribute, final Object ctx)
    {
        final boolean trace2 = m_log.atTRACE2 ();
        final boolean trace3 = m_log.atTRACE3 (); 
        if (trace2) m_log.trace2 ("visit", "attribute: [" + attribute.getName (m_cls) + "]");
        
        final int lineCount = attribute.size ();
        
        if (m_metadata)
        {
            if (trace2) m_log.trace2 ("visit", "processing line number table for metadata...");
            
            final int blockCount = m_classBlockCounts [m_methodID];
            if ($assert.ENABLED) $assert.ASSERT (blockCount > 0, "invalid method block count for method " + m_methodID);
            
            final int [][] blockLineMap = new int [blockCount][];
            
            if ($assert.ENABLED) $assert.ASSERT (blockCount + 1 == m_methodBlockOffsets.length,
                    "invalid m_methodBlockOffsets");
            
            if (lineCount == 0)
            {
                for (int bl = 0; bl < blockCount; ++ bl)
                    blockLineMap [bl] = EMPTY_INT_ARRAY;
            }
            else
            {
                // TODO: this code does not work if there are multiple LineNumberTableAttribute attributes for the method

                final LineNumber_info [] sortedLines = new LineNumber_info [attribute.size ()];
                
                for (int l = 0; l < lineCount; ++ l)
                {
                    final LineNumber_info line = attribute.get (l);
                    sortedLines [l] = line;
                }
                
                Arrays.sort (sortedLines, LINE_NUMBER_COMPARATOR);
                
                // construct block->line mapping: TODO: is the loop below the fastest it can be done?
                
                final int [] methodBlockOffsets = m_methodBlockOffsets;
                
                LineNumber_info line = sortedLines [0]; // never null
                LineNumber_info prev_line = null;
                
                // remember the first line:
                m_methodFirstLine = line.m_line_number;
                
                for (int bl = 0, l = 0; bl < blockCount; ++ bl)
                {                   
                    final IntSet blockLines = new IntSet ();
                    
                    if ((prev_line != null) && (line.m_start_pc > methodBlockOffsets [bl]))
                    {
                        blockLines.add (prev_line.m_line_number);
                    }
                    
                    while (line.m_start_pc < methodBlockOffsets [bl + 1])
                    {
                        blockLines.add (line.m_line_number);
                        
                        if (l == lineCount - 1)
                            break;
                        else
                        {
                            prev_line = line;
                            line = sortedLines [++ l]; // advance to the next line
                        }
                    }
                    
                    blockLineMap [bl] = blockLines.values ();
                }                
            }
            
            m_classBlockMetadata [m_methodID] = blockLineMap;
            
            if (trace3)
            {
                StringBuffer s = new StringBuffer ("block-line map for method #" + m_methodID + ":");
                for (int bl = 0; bl < blockCount; ++ bl)
                {
                    s.append (EOL);
                    s.append ("    block " + bl + ": ");
                    
                    final int [] lines = blockLineMap [bl];
                    for (int l = 0; l < lines.length; ++ l)
                    {
                        if (l != 0) s.append (", ");
                        s.append (lines [l]);
                    }
                }
                
                m_log.trace3 ("visit", s.toString ());
            }
        }
        
        for (int l = 0; l < lineCount; ++ l)
        {
            final LineNumber_info line = attribute.get (l);
            
            // TODO: make this faster using either table assist or the sorted array in 'sortedLines'
            
            // adjust bytecode offset for line number mapping:
            int adjSegment = lowbound (m_methodJumpAdjOffsets, line.m_start_pc);                
            line.m_start_pc += m_methodJumpAdjValues [adjSegment];
        }
        
        return ctx;
    }
    
    // TODO: line var table as well
    

    // no-op visits:

    public Object visit (final ExceptionsAttribute_info attribute, final Object ctx)
    {
        return ctx;
    }
    
    public Object visit (final ConstantValueAttribute_info attribute, final Object ctx)
    {
        return ctx;
    }
    
    public Object visit (final SourceFileAttribute_info attribute, final Object ctx)
    {
        m_classSrcFileName = attribute.getSourceFile (m_cls).m_value;

        return ctx;
    }

    public Object visit (final SyntheticAttribute_info attribute, final Object ctx)
    {
        return ctx;
    }
    
    public Object visit (final BridgeAttribute_info attribute, final Object ctx)
    {
        return ctx;
    }
    
    public Object visit (final InnerClassesAttribute_info attribute, final Object ctx)
    {
        return ctx;
    }
    
    public Object visit (final GenericAttribute_info attribute, final Object ctx)
    {
        return ctx;
    }
    
    // protected: .............................................................

    // package: ...............................................................
    
    // private: ...............................................................
    
    
    private static final class BlockList
    {
        BlockList ()
        {
            m_blocks = new ArrayList ();
        }
        
        BlockList (final int capacity)
        {
            m_blocks = new ArrayList (capacity);
        }
        
        final List /* Block */ m_blocks; // TODO: might as well use an array here?
        CodeSegment m_header;
        
    } // end of nested class 
    
    
    private static final class Block
    {
        int m_first;    // inclusive offset of the leader instruction [first instr in the block]
        //int m_last;     // exclusive offset of the last non-branch instruction [excludes possible control transfer at the end]
        int m_length;   // excluding the branch statement [can be 0]
        int m_instrCount; // size in instructions, including the [optional] original branch; [m_insertion is not counted] 
        
        // NOTE: it is possible that m_first == m_last [the block is empty except for a possible control transfer instr]
        
//        public int maxlength ()
//        {
//            // TODO: cache
//            return m_length
////                + (m_insertion != null ? m_insertion.maxlength () : 0)
//                + (m_branch != null ? m_branch.maxlength () : 0);
//        }
        
        /**
         * When this is called, all previous blocks have been written out and 
         * their m_first have been updated.
         */
        void emit (final EmitCtx ctx, final byte [] code) // TODO: move 'code' into 'ctx'
        {
            final ByteArrayOStream out = ctx.m_out;
            final int first = m_first;
            
            m_first = out.size (); // update position to be within new code array
            
            for (int i = 0, length = m_length; i < length; ++ i)
            {
                out.write (code [first + i]);
            }
            
            if (m_insertion != null)
                m_insertion.emit (ctx);
            
            if (m_branch != null)
                m_branch.emit (ctx);
        }
        
        public CodeSegment m_insertion;
        public Branch m_branch; // falling through is implied by this being null
        
    } // end of nested class
    
    
    static final class EmitCtx
    {
        // TODO: profile to check that ByteArrayOStream.write() is not the bottleneck
        
        EmitCtx (final BlockList blocks, final ByteArrayOStream out)
        {
            m_blocks = blocks;
            m_out = out;
            
            m_backpatchQueue = new ArrayList ();
        }
        
        final BlockList m_blocks;
        final ByteArrayOStream m_out;
        final List /* int[4] */ m_backpatchQueue;
        
    } // end of nested class
    
    
    /**
     * A Branch does not add any maxlocals/maxstack requirements.
     */
    static abstract class Branch
    {
        protected Branch (final int opcode, final int [] targets)
        {
            m_opcode = (byte) opcode;
            m_targets = targets;
        }
        
        /*
         * Called when targets are block IDs, before emitting. 
         */
        int maxlength () { return 1; }
        
        abstract void emit (EmitCtx ctx);
        
        // TODO: this method must signal when it is necessary to switch to long jump form
        protected final void emitJumpOffset2 (final EmitCtx ctx, final int ip, final int targetBlockID)
        {
            final ByteArrayOStream out = ctx.m_out;
            
            if (targetBlockID <= m_parentBlockID)
            {
                // backwards branch:
                final int jumpOffset = ((Block) ctx.m_blocks.m_blocks.get (targetBlockID)).m_first - ip;
                
                out.write2 (jumpOffset >>> 8,   // targetbyte1
                            jumpOffset);         // targetbyte2
            }
            else
            {
                final int jumpOffsetLocation = out.size (); 
                
                // else write out zeros and submit for backpatching:
                out.write2 (0,
                            0);
                
                ctx.m_backpatchQueue.add (new int [] {2, jumpOffsetLocation, ip, targetBlockID});
            }
        }
        
        protected final void emitJumpOffset4 (final EmitCtx ctx, final int ip, final int targetBlockID)
        {
            final ByteArrayOStream out = ctx.m_out;
            
            if (targetBlockID <= m_parentBlockID)
            {
                // backwards branch:
                final int jumpOffset = ((Block) ctx.m_blocks.m_blocks.get (targetBlockID)).m_first - ip;
                
                out.write4 (jumpOffset >>> 24,    // targetbyte1
                            jumpOffset >>> 16,    // targetbyte2
                            jumpOffset >>> 8,     // targetbyte3
                            jumpOffset);           // targetbyte4
            }
            else
            {
                final int jumpOffsetLocation = out.size (); 
                
                // else write out zeros and submit for backpatching:
                out.write4 (0,
                            0,
                            0,
                            0);
                
                ctx.m_backpatchQueue.add (new int [] {4, jumpOffsetLocation, ip, targetBlockID});
            }
        } 
        
        final byte m_opcode;
        final int [] m_targets; // could be code offsets or block IDs
        
        int m_parentBlockID;
        
    } // end of nested class    
    
    
    // TODO: these could be static instance-pooled
    static final class TERMINATE extends Branch // _[x]return, _athrow
    {
        TERMINATE (final int opcode)
        {
            super (opcode, null);
        }      
        
        int length () { return 1; }
        
        void emit (final EmitCtx ctx)
        {
            ctx.m_out.write (m_opcode);
        }
        
    } // end of nested class
    
    
    static final class RET extends Branch // [wide] ret
    {
        RET (final int opcode, final int varindex)
        {
            super (opcode, null);
            m_varindex = varindex;
        }      
        
        int length () { return (m_varindex <= 0xFF) ? 2 : 3; }
        
        void emit (final EmitCtx ctx)
        {
            final ByteArrayOStream out = ctx.m_out;
            
            if (m_varindex <= 0xFF)
            {
                out.write2 (m_opcode,
                            m_varindex);  // indexbyte
            }
            else
            {
                out.write4 (_wide,
                            m_opcode,
                            m_varindex >>> 8,   // indexbyte1
                            m_varindex);         // indexbyte2
            }
        }
        
        final int m_varindex;
        
    } // end of nested class
    
    
    static final class JUMP2 extends Branch // _goto, _jsr
    {
        JUMP2 (final int opcode, final int target)
        {
            super (opcode, new int [] {target});
        }
        
        int maxlength () { return 5; }
        
        void emit (final EmitCtx ctx)
        {
            final ByteArrayOStream out = ctx.m_out;
            final int targetBlockID = m_targets [0];
            final int ip = out.size ();
            
            // TODO: switch to 4-byte long form if jump > 32k
            
            out.write (m_opcode);
            emitJumpOffset2 (ctx, ip, targetBlockID);
        }
        
    } // end of nested class
    
    
    static final class JUMP4 extends Branch // _goto_w, _jsr_w
    {
        JUMP4 (final int opcode, final int target)
        {
            super (opcode, new int [] {target});
        }
        
        int maxlength () { return 5; }
        
        void emit (final EmitCtx ctx)
        {
            final ByteArrayOStream out = ctx.m_out;
            final int targetBlockID = m_targets [0];
            final int ip = out.size ();
            
            out.write (m_opcode);
            emitJumpOffset4 (ctx, ip, targetBlockID);
        }
        
    } // end of nested class
    
    
    static final class IFJUMP2 extends Branch // _ifxxx
    {
        IFJUMP2 (final int opcode, final int target)
        {
            super (opcode, new int [] {target});
        }
        
        int maxlength () { return 8; }
        
        void emit (final EmitCtx ctx)
        {
            final ByteArrayOStream out = ctx.m_out;
            final int targetBlockID = m_targets [0];
            final int ip = out.size ();
            
            // TODO: switch to 8-byte long form if jump > 32k
            
            out.write (m_opcode);
            emitJumpOffset2 (ctx, ip, targetBlockID);
        }
        
    } // end of nested class

    
    static final class LOOKUPSWITCH extends Branch
    {
        LOOKUPSWITCH (final int [] keys, final int [] targets /* first one is default */)
        {
            super (_lookupswitch, targets);
            m_keys = keys;
        }
        
        int maxlength () { return 12 + (m_keys.length << 3); }
        
        void emit (final EmitCtx ctx)
        {
            final ByteArrayOStream out = ctx.m_out;
            final int ip = out.size ();
            
            out.write (m_opcode);
            
            // padding bytes:
            for (int p = 0, padCount = 3 - (ip & 3); p < padCount; ++ p) out.write (0);
             
            // default:
            emitJumpOffset4 (ctx, ip, m_targets [0]);
            
            // npairs count:
            final int npairs = m_keys.length;
            out.write4 (npairs >>> 24,  // byte1
                        npairs >>> 16,  // byte2
                        npairs >>> 8,   // byte3
                        npairs);        // byte4
            
            // keyed targets:
            for (int t = 1; t < m_targets.length; ++ t)
            {
                final int key = m_keys [t - 1];
                out.write4 (key >>> 24,  // byte1
                            key >>> 16,  // byte2
                            key >>> 8,   // byte3
                            key);         // byte4

                // key target:
                emitJumpOffset4 (ctx, ip, m_targets [t]); 
            }
        }
        
        final int [] m_keys;
        
    } // end of nested class


    static final class TABLESWITCH extends Branch
    {
        TABLESWITCH (final int low, final int high, final int [] targets /* first one is default */)
        {
            super (_tableswitch, targets);
            m_low = low;
            m_high = high;
        }
        
        int maxlength () { return 12 + (m_targets.length << 2); }
        
        void emit (final EmitCtx ctx)
        {
            final ByteArrayOStream out = ctx.m_out;
            final int ip = out.size ();
            
            // TODO: switch to long form for any jump > 32k
            
            out.write (m_opcode);
            
            // padding bytes:
            for (int p = 0, padCount = 3 - (ip & 3); p < padCount; ++ p) out.write (0);
             
            // default:
            emitJumpOffset4 (ctx, ip, m_targets [0]);
                        
            // low, high:
            final int low = m_low;
            out.write4 (low >>> 24,  // byte1
                        low >>> 16,  // byte2
                        low >>> 8,   // byte3
                        low);        // byte4
            
            final int high = m_high;
            out.write4 (high >>> 24,  // byte1
                        high >>> 16,  // byte2
                        high >>> 8,   // byte3
                        high);        // byte4
                        
            // targets:
            for (int t = 1; t < m_targets.length; ++ t)
            {
                // key target:
                emitJumpOffset4 (ctx, ip, m_targets [t]); 
            }
        }
            
        final int m_low, m_high;
            
    } // end of nested class
    
    
    /**
     * TODO: CodeSegment right now must be 100% position-independent code;
     * otherwise it must follow maxlengtt() Branch pattern... 
     */
    static abstract class CodeSegment
    {
        CodeSegment (final InstrVisitor visitor)
        {
            m_visitor = visitor; // TODO: will this field be used?
        }
        
        abstract int length ();
        abstract int maxstack ();
        abstract void emit (EmitCtx ctx);
        
        
        final InstrVisitor m_visitor;
        
    } // end of nested class
    
    
    static final class clinitHeader extends CodeSegment
    {
        clinitHeader (final InstrVisitor visitor, final int localVarIndex)
        {
            super (visitor);
            final ByteArrayOStream buf = new ByteArrayOStream (CLINIT_HEADER_INIT_CAPACITY); 
            m_buf = buf;
            
            final ClassDef cls = visitor.m_cls;
            
            final int [] blockCounts = visitor.m_classBlockCounts;
            final int instrMethodCount = visitor.m_classInstrMethodCount; // actual number of methods to instrument may be less than the size of the block map 
            if ($assert.ENABLED) $assert.ASSERT (blockCounts != null && blockCounts.length >= instrMethodCount,
                "invalid block count map");
            
            final int coverageFieldrefIndex = visitor.m_coverageFieldrefIndex;
            final int preclinitMethodrefIndex = visitor.m_preclinitMethodrefIndex;
            final int classNameConstantIndex = visitor.m_classNameConstantIndex;
            
            if ($assert.ENABLED)
            {
                $assert.ASSERT (coverageFieldrefIndex > 0, "invalid coverageFieldrefIndex");
                $assert.ASSERT (preclinitMethodrefIndex > 0, "invalid registerMethodrefIndex");
                $assert.ASSERT (classNameConstantIndex > 0, "invalid classNameConstantIndex");
            }

            // init and load COVERAGE_FIELD:   
            buf.write3 (_invokestatic,
                        preclinitMethodrefIndex >>> 8,    // indexbyte1
                        preclinitMethodrefIndex);         // indexbyte2

            // [stack +1]

            // TODO: disable this when there are no real blocks following?
            // [in general, use a different template when this method contains a single block]

            // TODO: if this method has been added by us, do not instrument its blocks
            
            // push int literal equal to 'methodID' [for the parent method]:
            CodeGen.push_int_value (buf, cls, visitor.m_methodID);
            
            // [stack +2]
            
            // push subarray reference:
            buf.write (_aaload);
            
            // [stack +1]
            
            // store it in alias var:
            CodeGen.store_local_object_var (buf, localVarIndex);
            
            // [stack +0]            
        }
        
        int length () { return m_buf.size (); }
        int maxstack () { return 2; } // note: needs to be updated each time emitted code changes
        
        void emit (final EmitCtx ctx)
        {
            // TODO: better error handling here?
            try
            {
                m_buf.writeTo (ctx.m_out);
            }
            catch (IOException ioe)
            {
                if ($assert.ENABLED) $assert.ASSERT (false, ioe.toString ());
            }
        }
        
        
        private final ByteArrayOStream m_buf;
        
        private static final int CLINIT_HEADER_INIT_CAPACITY = 32; // covers about 80% of classes (no reallocation)
        
    } // end of nested class
    
    
    static final class methodHeader extends CodeSegment
    {
        methodHeader (final InstrVisitor visitor, final int localVarIndex)
        {
            super (visitor);
            final ByteArrayOStream buf = new ByteArrayOStream (HEADER_INIT_CAPACITY);
            m_buf = buf;
            
            final ClassDef cls = visitor.m_cls;
            final int coverageFieldrefIndex = visitor.m_coverageFieldrefIndex;
            final int preclinitMethodrefIndex = visitor.m_preclinitMethodrefIndex;

            // TODO: disable this when there are no real blocks following?
            // [in general, use a different template when this method contains a single block]

            // push ref to the static field and dup it:
            buf.write4 (_getstatic,
                        coverageFieldrefIndex >>> 8, // indexbyte1
                        coverageFieldrefIndex,       // indexbyte2
                        _dup);
            
            // [stack +2]
            
            // SF FR 971186: check if it is null and if so run the field
            // init and class RT register code (only relevant for
            // methods that can be executed ahead of <clinit>) [rare] 
            
            buf.write3 (_ifnonnull, // skip over pre-<clinit> method call
                        0,
                        3 + /* size of the block below */ 4);
                        
            // [stack +1]
            
            // block: call pre-<clinit> method
            {
                buf.write4 (_pop,
                            _invokestatic,
                            preclinitMethodrefIndex >>> 8,    // indexbyte1
                            preclinitMethodrefIndex);         // indexbyte2
                            
                // [stack +1]
            }

            // push int literal equal to 'methodID':
            CodeGen.push_int_value (buf, cls, visitor.m_methodID);
            
            // [stack +2]
            
            // push subarray reference:
            buf.write (_aaload);
            
            // [stack +1]
            
            // store it in alias var:
            CodeGen.store_local_object_var (buf, localVarIndex);
            
            // [stack +0]            
        }
        
        int length () { return m_buf.size (); }
        int maxstack () { return 2; } // note: needs to be updated each time emitted code changes
        
        void emit (final EmitCtx ctx)
        {
            // TODO: better error handling here?
            try
            {
                m_buf.writeTo (ctx.m_out);
            }
            catch (IOException ioe)
            {
                if ($assert.ENABLED) $assert.ASSERT (false, ioe.toString ());
            }
        }
        
        
        private final ByteArrayOStream m_buf;
        
        private static final int HEADER_INIT_CAPACITY = 16;
        
    } // end of nested class
    
    
    static final class BlockSegment extends CodeSegment
    {
        public BlockSegment (final InstrVisitor visitor, final int localVarIndex, final int blockID)
        {
            super (visitor);
            final ByteArrayOStream buf = new ByteArrayOStream (BLOCK_INIT_CAPACITY); 
            m_buf = buf;
                        
            final ClassDef cls = visitor.m_cls;
            
            // push alias var:
            CodeGen.load_local_object_var (buf, localVarIndex);
            
            // [stack +1]
            
            // push int value equal to 'blockID':
            CodeGen.push_int_value (buf, cls, blockID);
            
            // [stack +2]
            
            // push boolean 'true':
            buf.write2 (_iconst_1,
            
            // [stack +3]
            
            // store it in the array:
                        _bastore);
            
            // [stack +0]
        }
        
        int length () { return m_buf.size (); }
        int maxstack () { return 3; } // note: needs to be updated each time emitted code changes
        
        void emit (final EmitCtx ctx)
        {
            // TODO: better error handling here?
            try
            {
                m_buf.writeTo (ctx.m_out);
            }
            catch (IOException ioe)
            {
                if ($assert.ENABLED) $assert.ASSERT (false, ioe.toString ());
            }
        }
        
        
        private final ByteArrayOStream m_buf;
        
        private static final int BLOCK_INIT_CAPACITY = 16;
        
    } // end of nested class
    
    
    private static final class LineNumberComparator implements Comparator
    {
        public final int compare (final Object o1, final Object o2)
        {
            return ((LineNumber_info) o1).m_start_pc - ((LineNumber_info) o2).m_start_pc;
        }
        
    } // end of nested class
  
  
    private void setClassName (final String fullName)
    {
        if ($assert.ENABLED) $assert.ASSERT (fullName != null && fullName.length () > 0,
            "null or empty input: fullName");
        
        final int lastSlash = fullName.lastIndexOf ('/');
        if (lastSlash < 0)
        {
            m_classPackageName = "";
            m_className = fullName;
        }
        else
        {
            if ($assert.ENABLED) $assert.ASSERT (lastSlash < fullName.length () - 1,
                "malformed class name [" + fullName + "]");
            
            m_classPackageName = fullName.substring (0, lastSlash);
            m_className = fullName.substring (lastSlash + 1);
        }   
    }
    
    private void consumeSignatureData (final int methodID, final int [] basicBlockOffsets)
    {
        // note: by itself, this is not a very good checksum for a class def;
        // however, it is fast to compute and since it will be used along with
        // a class name it should be good at detecting structural changes that
        // matter to us (method and basic block ordering/sizes) 
        
        final int temp1 = basicBlockOffsets.length;
        long temp2 = NBEAST * m_classSignature + (methodID + 1) * temp1;
        
        for (int i = 1; i < temp1; ++ i) // skip the initial 0 offset
        {
            temp2 = NBEAST * temp2 + basicBlockOffsets [i];
        }
        
        m_classSignature = temp2;
    }
     
    // TODO: use a compilation flag to use table assist here instead of binary search
    // BETTER YET: use binsearch for online mode and table assist for offline [when memory is not an issue]
  
    /**
     * Returns the maximum index 'i' such that (values[i] <= x). values[]
     * contains distinct non-negative integers in increasing order. values[0] is 0,
     * 'x' is non-negative.
     * 
     * Edge case:
     *  returns values.length-1 if values [values.length - 1] < x
     */
    private static int lowbound (final int [] values, final int x)
    {
        int low = 0, high = values.length - 1;
        
        // assertion: lb is in [low, high]
        
        while (low <= high)
        {
            final int m = (low + high) >> 1;
            final int v = values [m];
            
            if (v == x)
                return m;
            else if (v < x)
                low = m + 1;
            else // v > x
                high = m - 1;
        }
        
        return high;
    }
    
    private void reset ()
    {
        // TODO: check that all state is reset
        
        m_instrument = false;
        m_metadata = false;
        m_ignoreAlreadyInstrumented = false;
        
        m_cls = null;
        m_classPackageName = null;
        m_className = null;
        m_classSrcFileName = null;
        m_classBlockMetadata = null;
        m_classMethodDescriptors = null;
        
        m_syntheticStringIndex = -1;
        m_coverageFieldrefIndex = -1;
        m_registerMethodrefIndex = -1;
        m_preclinitMethodrefIndex = -1;
        m_classNameConstantIndex = -1;
        m_clinitID = -1;
        m_clinitStatus = 0;
        m_classInstrMethodCount = -1;
        m_classBlockCounts = null;
        m_classSignature = 0;
        
        m_methodID = -1;
        m_methodName = null;
        m_methodFirstLine = 0;
        m_methodBlockOffsets = null;
        m_methodJumpAdjOffsets = null;
        m_methodJumpAdjValues = null;
    }
    
    
    private final boolean m_excludeSyntheticMethods;
    private final boolean m_excludeBridgeMethods;
    private final boolean m_doSUIDCompensation;
    
    private final Logger m_log; // instr visitor logging context is latched at construction time
    
    // non-resettable state:
    
    private boolean m_warningIssued;
    
    
    // resettable state:
    
    private boolean m_instrument;
    private boolean m_metadata;
    private boolean m_ignoreAlreadyInstrumented;
    
    /*private*/ ClassDef m_cls;
    private String m_classPackageName; // in JVM format [com/vladium/...]; empty string for default package
    private String m_className; // in JVM format [<init>, <clinit>, etc], relative to 'm_classPackageName'
    private String m_classSrcFileName;
    private int [][][] m_classBlockMetadata; // methodID->(blockID->line) map [valid only if 'm_constructMetadata' is true; null if the method has not line number table]
    private MethodDescriptor [] m_classMethodDescriptors;
    
    // current class scope: 
    private int m_syntheticStringIndex;     // index of CONSTANT_Utf8 String that reads "Synthetic"     
    /*private*/ int m_coverageFieldrefIndex;    // index of the Fieldref for COVERAGE_FIELD
    private int m_registerMethodrefIndex;   // index of Methodref for RT.r()
    /*private*/ int m_preclinitMethodrefIndex;  // index of Methodref for pre-<clinit> method
    /*private*/ int m_classNameConstantIndex;   // index of CONSTANT_String that is the class name [in JVM format]
    private int m_stampIndex;               // index of CONSTANT_Long that is the class instr stamp
    private int m_clinitID;                 // offset of <clinit> method [-1 if not determined yet]
    private int m_clinitStatus;
    /*private*/ int m_classInstrMethodCount;    // the number of slots in 'm_classBlockCounts' corresponding to methods to be instrumented for coverage
    /*private*/ int [] m_classBlockCounts;      // basic block counts for all methods [only valid just before <clinit> is processed]
    private long m_classSignature;
    
    // current method scope: 
    /*private*/ int m_methodID;                 // offset of current method being instrumented
    private String m_methodName;
    private int m_methodFirstLine;
    private int [] m_methodBlockOffsets;    // [unadjusted] basic block boundaries [length = m_classBlockCounts[m_methodID]+1; the last slot is method bytecode length]
    private int [] m_methodBlockSizes;
    private int [] m_methodJumpAdjOffsets;    // TODO: length ?
    private int [] m_methodJumpAdjValues;        // TODO: length ?
    
    
    private static final long NBEAST = 16661; // prime

    private static final String COVERAGE_FIELD_NAME = "$VR" + "c";
    private static final String SUID_FIELD_NAME = "serialVersionUID";
    private static final String PRECLINIT_METHOD_NAME = "$VR" + "i";

    private static final String JAVA_IO_SERIALIZABLE_NAME = "java/io/Serializable";
    private static final String JAVA_IO_EXTERNALIZABLE_NAME = "java/io/Externalizable";
    
    private static final int EMIT_CTX_MIN_INIT_CAPACITY = 64; // good value determined empirically
    private static final int PRECLINIT_INIT_CAPACITY = 128; // covers about 80% of classes (no reallocation)
    private static final boolean MARK_ADDED_ELEMENTS_SYNTHETIC = true;
    
    /* It appears that nested classes and interfaces ought to be marked
     * as Synthetic; however, neither Sun nor IBM compilers seem to do this.
     * 
     * (As a side note, implied no-arg constructors ought to be marked as
     * synthetic as well, but Sun's javac is not consistent about that either)  
     */
    private static final boolean SKIP_SYNTHETIC_CLASSES = false;
    
    private static final LineNumberComparator LINE_NUMBER_COMPARATOR = new LineNumberComparator ();
    
    private static final byte [] EMPTY_BYTE_ARRAY = new byte [0];

} // end of class
// ----------------------------------------------------------------------------