Logo Search packages:      
Sourcecode: eclipse-cdt version File versions  Download package

CPPTemplates.java

/*******************************************************************************
 * Copyright (c) 2005 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 * IBM - Initial API and implementation
 *******************************************************************************/
/*
 * Created on Mar 11, 2005
 */
package org.eclipse.cdt.internal.core.dom.parser.cpp;

import org.eclipse.cdt.core.dom.ast.DOMException;
import org.eclipse.cdt.core.dom.ast.IASTCompositeTypeSpecifier;
import org.eclipse.cdt.core.dom.ast.IASTDeclSpecifier;
import org.eclipse.cdt.core.dom.ast.IASTDeclaration;
import org.eclipse.cdt.core.dom.ast.IASTDeclarator;
import org.eclipse.cdt.core.dom.ast.IASTElaboratedTypeSpecifier;
import org.eclipse.cdt.core.dom.ast.IASTExpression;
import org.eclipse.cdt.core.dom.ast.IASTFunctionDefinition;
import org.eclipse.cdt.core.dom.ast.IASTLiteralExpression;
import org.eclipse.cdt.core.dom.ast.IASTName;
import org.eclipse.cdt.core.dom.ast.IASTNode;
import org.eclipse.cdt.core.dom.ast.IASTParameterDeclaration;
import org.eclipse.cdt.core.dom.ast.IASTSimpleDeclaration;
import org.eclipse.cdt.core.dom.ast.IASTStatement;
import org.eclipse.cdt.core.dom.ast.IArrayType;
import org.eclipse.cdt.core.dom.ast.IBasicType;
import org.eclipse.cdt.core.dom.ast.IBinding;
import org.eclipse.cdt.core.dom.ast.IFunction;
import org.eclipse.cdt.core.dom.ast.IFunctionType;
import org.eclipse.cdt.core.dom.ast.IParameter;
import org.eclipse.cdt.core.dom.ast.IPointerType;
import org.eclipse.cdt.core.dom.ast.IProblemBinding;
import org.eclipse.cdt.core.dom.ast.IQualifierType;
import org.eclipse.cdt.core.dom.ast.IScope;
import org.eclipse.cdt.core.dom.ast.IType;
import org.eclipse.cdt.core.dom.ast.ITypedef;
import org.eclipse.cdt.core.dom.ast.cpp.CPPASTVisitor;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTCompositeTypeSpecifier;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTDeclSpecifier;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTElaboratedTypeSpecifier;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTExplicitTemplateInstantiation;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTFunctionDeclarator;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTNamedTypeSpecifier;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTParameterDeclaration;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTQualifiedName;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTSimpleTypeTemplateParameter;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTTemplateDeclaration;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTTemplateId;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTTemplateParameter;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTTemplateSpecialization;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPASTTemplatedTypeTemplateParameter;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPClassTemplate;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPClassTemplatePartialSpecialization;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPClassType;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPConstructor;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPField;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPFunction;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPFunctionTemplate;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPFunctionType;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPMethod;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPPointerToMemberType;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPReferenceType;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPScope;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPSpecialization;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateDefinition;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateInstance;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateNonTypeParameter;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateParameter;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateScope;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateTemplateParameter;
import org.eclipse.cdt.core.dom.ast.cpp.ICPPTemplateTypeParameter;
import org.eclipse.cdt.core.parser.util.ArrayUtil;
import org.eclipse.cdt.core.parser.util.CharArrayUtils;
import org.eclipse.cdt.core.parser.util.ObjectMap;
import org.eclipse.cdt.core.parser.util.ObjectSet;
import org.eclipse.cdt.internal.core.dom.parser.ITypeContainer;
import org.eclipse.cdt.internal.core.dom.parser.ProblemBinding;
import org.eclipse.cdt.internal.core.dom.parser.cpp.CPPSemantics.Cost;

/**
 * @author aniefer
 */
00088 public class CPPTemplates {

      public static IASTName getTemplateParameterName( ICPPASTTemplateParameter param ){
            if( param instanceof ICPPASTSimpleTypeTemplateParameter )
                  return ((ICPPASTSimpleTypeTemplateParameter)param).getName();
            else if( param instanceof ICPPASTTemplatedTypeTemplateParameter )
                  return ((ICPPASTTemplatedTypeTemplateParameter)param).getName();
            else if( param instanceof ICPPASTParameterDeclaration )
                  return ((ICPPASTParameterDeclaration)param).getDeclarator().getName();
            return null;
      }
      
      private static ICPPTemplateDefinition getContainingTemplate( ICPPASTTemplateParameter param ){
            IASTNode parent = param.getParent();
            IBinding binding = null;
            if( parent instanceof ICPPASTTemplateDeclaration ){
//                IASTName name = getTemplateName( (ICPPASTTemplateDeclaration) parent );
//                if( name != null ){
//                      if( name instanceof ICPPASTTemplateId && !(name.getParent() instanceof ICPPASTQualifiedName) )
//                            name = ((ICPPASTTemplateId)name).getTemplateName();
//                            
//                      binding = name.resolveBinding();
//                }
                  ICPPASTTemplateDeclaration [] templates = new ICPPASTTemplateDeclaration [] { (ICPPASTTemplateDeclaration) parent };
                  
                  while( parent.getParent() instanceof ICPPASTTemplateDeclaration ){
                        parent = parent.getParent();
                        templates = (ICPPASTTemplateDeclaration[]) ArrayUtil.append( ICPPASTTemplateDeclaration.class, templates, parent );
                  }
                  templates = (ICPPASTTemplateDeclaration[]) ArrayUtil.trim( ICPPASTTemplateDeclaration.class, templates );
                  
                  ICPPASTTemplateDeclaration templateDeclaration = templates[0];
                  IASTDeclaration decl = templateDeclaration.getDeclaration();
                  while( decl instanceof ICPPASTTemplateDeclaration )
                        decl = ((ICPPASTTemplateDeclaration)decl).getDeclaration();
                  
                  IASTName name = null;
                  if( decl instanceof IASTSimpleDeclaration ){
                        IASTSimpleDeclaration simpleDecl = (IASTSimpleDeclaration) decl;
                        IASTDeclarator [] dtors = ((IASTSimpleDeclaration)decl).getDeclarators();
                        if( dtors.length == 0 ){
                              IASTDeclSpecifier spec = simpleDecl.getDeclSpecifier();
                              if( spec instanceof ICPPASTCompositeTypeSpecifier ){
                                    name = ((ICPPASTCompositeTypeSpecifier)spec).getName();
                              } else if( spec instanceof ICPPASTElaboratedTypeSpecifier ){
                                    name = ((ICPPASTElaboratedTypeSpecifier)spec).getName();
                              }
                        } else {
                              IASTDeclarator dtor = dtors[0];
                              while( dtor.getNestedDeclarator() != null )
                                    dtor = dtor.getNestedDeclarator();
                              name = dtor.getName();
                        }
                  } else if( decl instanceof IASTFunctionDefinition ){
                        IASTDeclarator dtor = ((IASTFunctionDefinition)decl).getDeclarator();
                        while( dtor.getNestedDeclarator() != null )
                              dtor = dtor.getNestedDeclarator();
                        name = dtor.getName();
                  }
                  if( name == null )
                        return null;
                        
                  if( name instanceof ICPPASTQualifiedName ){
                        int idx = templates.length;
                        int i = 0;
                        IASTName [] ns = ((ICPPASTQualifiedName) name).getNames();
                        for (int j = 0; j < ns.length; j++) {
                              if( ns[j] instanceof ICPPASTTemplateId ){
                                    ++i;
                                    if( i == idx ){
                                          binding = ((ICPPASTTemplateId)ns[j]).getTemplateName().resolveBinding();
                                          break;
                                    }
                              }
                        }
                        if( binding == null )
                              binding = ns[ ns.length - 1 ].resolveBinding();
                  } else {
                        binding = name.resolveBinding();
                  }
            } else if( parent instanceof ICPPASTTemplatedTypeTemplateParameter ){
                  ICPPASTTemplatedTypeTemplateParameter templatedParam = (ICPPASTTemplatedTypeTemplateParameter) parent;
                  binding = templatedParam.getName().resolveBinding();
            }
            return  (binding instanceof ICPPTemplateDefinition) ? (ICPPTemplateDefinition) binding : null;
      }
      public static IBinding createBinding( ICPPASTTemplateParameter templateParameter ){
            ICPPTemplateDefinition template = getContainingTemplate( templateParameter );
            
            IBinding binding = null;
            if( template instanceof CPPTemplateDefinition ){
                  binding = ((CPPTemplateDefinition)template).resolveTemplateParameter( templateParameter );
            } else if( template instanceof CPPTemplateTemplateParameter ){
                  binding = ((CPPTemplateTemplateParameter)template).resolveTemplateParameter( templateParameter );
            }
                    
          return binding;
      }
      static public ICPPScope getContainingScope( IASTNode node ){
            while( node != null ){
                  if( node instanceof ICPPASTTemplateParameter ){
                        IASTNode parent = node.getParent();
                        if( parent instanceof ICPPASTTemplateDeclaration ){
                              return ((ICPPASTTemplateDeclaration)parent).getScope();
                        }
                  }
                  node = node.getParent();
            }
            
            return null;
      }

      /**
       * @param id
       * @return
       */
00204       public static IBinding createBinding(ICPPASTTemplateId id) {
            IASTNode parent = id.getParent();
            int segment = -1;
            if( parent instanceof ICPPASTQualifiedName ){
                  IASTName [] ns = ((ICPPASTQualifiedName)parent).getNames();
                  segment = ( ns[ ns.length - 1 ] == id ) ? 1 : 0;
                  parent = parent.getParent();
            }

            IASTNode decl = parent.getParent();
            while( !(decl instanceof IASTDeclaration) )
                  decl = decl.getParent();
            decl = decl.getParent();
                  
            if( decl instanceof ICPPASTExplicitTemplateInstantiation &&
                  parent instanceof ICPPASTElaboratedTypeSpecifier && segment != 0 )
            {
                return createClassExplicitInstantiation( (ICPPASTElaboratedTypeSpecifier) parent );
            } else if( (parent instanceof ICPPASTElaboratedTypeSpecifier ||
                            parent instanceof ICPPASTCompositeTypeSpecifier ) && segment != 0 ){
                  return createClassSpecialization( (ICPPASTDeclSpecifier) parent );
            } else if( parent instanceof ICPPASTFunctionDeclarator && segment != 0 ){
                  return createFunctionSpecialization( id );
            }
            
            //a reference: class or function template?
            IBinding template = null;
            if( parent instanceof ICPPASTNamedTypeSpecifier || segment == 0 ){
                  //class template
                  IASTName templateName = id.getTemplateName();
                  template = templateName.resolveBinding();
                  if( template instanceof ICPPClassTemplatePartialSpecialization ){
                        //specializations are selected during the instantiation, start with the primary template
                        try {
                              template = ((ICPPClassTemplatePartialSpecialization)template).getPrimaryClassTemplate();
                        } catch (DOMException e) {
                              return e.getProblem();
                        }
                  } else if( template instanceof ICPPSpecialization && !(template instanceof ICPPTemplateDefinition) ){
                        template = ((ICPPSpecialization)template).getSpecializedBinding();
                  }
                  
                  if( template != null && template instanceof ICPPInternalTemplate ){
                        IASTNode [] args = id.getTemplateArguments();
                        IType [] types = CPPTemplates.createTypeArray( args );
                        return ((ICPPInternalTemplate)template).instantiate( types );
                  }
            } else {
                  //functions are instatiated as part of the resolution process
                  template = CPPVisitor.createBinding( id );
                  if( template instanceof ICPPTemplateInstance ){
                        IASTName templateName = id.getTemplateName();
                        templateName.setBinding( ((ICPPTemplateInstance)template).getTemplateDefinition() );
                  }
            }
            
            return template;
      }

      protected static IBinding createClassExplicitInstantiation( ICPPASTElaboratedTypeSpecifier elabSpec ){
          IASTName name = elabSpec.getName();
          if( name instanceof ICPPASTQualifiedName ){
                  IASTName [] ns = ((ICPPASTQualifiedName)name).getNames();
                  name = ns[ ns.length - 1 ];
            }
          ICPPASTTemplateId id = (ICPPASTTemplateId) name;
          IBinding template = id.getTemplateName().resolveBinding();
            if( !(template instanceof ICPPClassTemplate) ) 
                  return null;  //TODO: problem?
            
            ICPPClassTemplate classTemplate = (ICPPClassTemplate) template;
            IType [] args = createTypeArray( id.getTemplateArguments() );
            if( classTemplate instanceof ICPPInternalTemplate ){
                IBinding binding = ((ICPPInternalTemplate)classTemplate).instantiate( args );
                return binding;
            }
            return null;
      }
      protected static IBinding createClassSpecialization( ICPPASTDeclSpecifier compSpec ){
            IASTName name = null;
            if( compSpec instanceof ICPPASTElaboratedTypeSpecifier )
                  name = ((ICPPASTElaboratedTypeSpecifier)compSpec).getName();
            else if( compSpec instanceof ICPPASTCompositeTypeSpecifier )
                  name = ((ICPPASTCompositeTypeSpecifier)compSpec).getName();
            else 
                  return null;
            
            if( name instanceof ICPPASTQualifiedName ){
                  IASTName [] ns = ((ICPPASTQualifiedName)name).getNames();
                  name = ns[ ns.length - 1 ];
            }
            ICPPASTTemplateId id = (ICPPASTTemplateId) name;
            
            IBinding binding = id.getTemplateName().resolveBinding();
            if( !(binding instanceof ICPPClassTemplate) ) 
                  return null;  //TODO: problem?
            
            ICPPClassTemplate template = (ICPPClassTemplate) binding;
            
            IBinding spec = null;
            ICPPASTTemplateDeclaration templateDecl = getTemplateDeclaration( id );
            if( templateDecl instanceof ICPPASTTemplateSpecialization ){
                  //specialization
                  ICPPTemplateParameter [] templateParams = null;
                  try {
                        templateParams = template.getTemplateParameters();
                  } catch (DOMException e) {
                        return e.getProblem();
                  }
                  IType [] args = createTypeArray( id.getTemplateArguments() );
                  ObjectMap argMap = new ObjectMap( templateParams.length );
                  if( templateParams.length != args.length ){
                        return null; //TODO problem
                  }
                  for (int i = 0; i < templateParams.length; i++) {
                        argMap.put( templateParams[i], args[i] );
                  }
                  if( template instanceof ICPPInternalTemplate ){
                        spec = ((ICPPInternalTemplate)template).getInstance( args );
                  }
                  if( spec == null ) {
                        ICPPScope scope = (ICPPScope) CPPVisitor.getContainingScope( id );
                        spec = new CPPClassSpecialization(binding, scope, argMap );
                        ((ICPPInternalTemplate)template).addSpecialization( args, (ICPPSpecialization) spec );
                  }
                  IASTNode parent = id.getParent();
                  while( !(parent instanceof IASTDeclSpecifier ) )
                        parent = parent.getParent();
                  if( parent instanceof IASTElaboratedTypeSpecifier )
                        ((ICPPInternalBinding)spec).addDeclaration( id );
                  else if( parent instanceof IASTCompositeTypeSpecifier )
                        ((ICPPInternalBinding)spec).addDefinition( id );
                  return spec;
            } 
            //else partial specialization
            //CPPClassTemplate template = (CPPClassTemplate) binding;
            ICPPClassTemplatePartialSpecialization [] specializations = null;
            try {
                  specializations = template.getPartialSpecializations();
            } catch (DOMException e) {
            }
            if( specializations != null ) {
                  for (int i = 0; i < specializations.length; i++) {
                        if( isSameTemplate( specializations[i], id ) ){
                              spec = specializations[i];
                              break;
                        }
                  }
            }
            
            if( spec != null ){
                  ((ICPPInternalBinding)spec).addDefinition( id );
                  return spec;
            }
            
            spec = new CPPClassTemplatePartialSpecialization( id );
            ((CPPClassTemplate)template).addPartialSpecialization( (ICPPClassTemplatePartialSpecialization) spec );
            return spec;
      }
      
      protected static IBinding createFunctionSpecialization( IASTName name ){
            CPPSemantics.LookupData data = new CPPSemantics.LookupData( name );
            data.forceQualified = true;
            ICPPScope scope = (ICPPScope) CPPVisitor.getContainingScope( name );
            if( scope instanceof ICPPTemplateScope ){
                  try {
                        scope = (ICPPScope) scope.getParent();
                  } catch (DOMException e) {
                  }
            }
            try {
                  CPPSemantics.lookup( data, scope );
            } catch (DOMException e) {
                  return e.getProblem();
            }

            ICPPFunctionTemplate function = resolveTemplateFunctions( (Object[]) data.foundItems, name );
            if( function == null )
                  return new ProblemBinding( name, IProblemBinding.SEMANTIC_NAME_NOT_FOUND, name.toCharArray() );
            if( function instanceof IProblemBinding )
                  return function;
            
            if( name instanceof ICPPASTTemplateId ){
                  ((ICPPASTTemplateId)name).getTemplateName().setBinding( function );
            }
            IASTNode parent = name.getParent();
            while( parent instanceof IASTName )
                  parent = parent.getParent();
            
            IASTParameterDeclaration [] ps = ((ICPPASTFunctionDeclarator)parent).getParameters();
            Object [] map_types;
            try {
                  map_types = deduceTemplateFunctionArguments( function, ps, data.templateArguments );
            } catch (DOMException e) {
                  return e.getProblem();
            }
            if( map_types != null ){
                while( !(parent instanceof IASTDeclaration ) )
                        parent = parent.getParent();
                
                ICPPSpecialization spec = null;
                if( parent.getParent() instanceof ICPPASTExplicitTemplateInstantiation ){
                  spec = ((ICPPInternalTemplate)function).getInstance( (IType[])map_types[1] );
                  if( spec == null )
                        spec = (ICPPSpecialization) CPPTemplates.createInstance( scope, function, (ObjectMap)map_types[0], (IType[])map_types[1] );
                } else {
                  spec = ((ICPPInternalTemplate)function).getInstance( (IType[])map_types[1] );
                  if( spec == null ) {
                        if( function instanceof ICPPConstructor )
                              spec = new CPPConstructorSpecialization( function, scope, (ObjectMap) map_types[0] );
                              else if( function instanceof ICPPMethod )
                                    spec = new CPPMethodSpecialization( function, scope, (ObjectMap) map_types[0] );
                              else 
                                    spec = new CPPFunctionSpecialization( function, scope, (ObjectMap) map_types[0] );
                  }
                        
                        if( parent instanceof IASTSimpleDeclaration )
                              ((ICPPInternalBinding)spec).addDeclaration( name );
                        else if( parent instanceof IASTFunctionDefinition )
                              ((ICPPInternalBinding)spec).addDefinition( name );
                }
                ((ICPPInternalTemplate)function).addSpecialization( (IType[]) map_types[1], spec );
                return spec;
            }
            //TODO problem?
            return null;      
      }
      
      static protected ICPPFunctionTemplate resolveTemplateFunctions( Object [] items, IASTName name ) {
            if( items == null )
                  return null;
            ICPPFunctionTemplate [] templates = null;
            IBinding temp = null;
            for( int i = 0; i < items.length; i++ ){
                  Object o = items[i];
              
              if( o instanceof IASTName ){
                  temp = ((IASTName) o).resolveBinding();
                  if( temp == null )
                      continue;
              } else if( o instanceof IBinding ){
                  temp = (IBinding) o;
              } else
                  continue;
                  
                  if( temp instanceof ICPPTemplateInstance )
                        temp = ((ICPPTemplateInstance)temp).getTemplateDefinition();
                  if( temp instanceof ICPPFunctionTemplate )
                        templates = (ICPPFunctionTemplate[]) ArrayUtil.append( ICPPFunctionTemplate.class, templates, temp );
            }
            
            if( templates == null )
                  return null;
            
            IType [] templateArguments = null;
            
            if( name instanceof ICPPASTTemplateId ){
                  templateArguments = createTypeArray( ((ICPPASTTemplateId)name).getTemplateArguments() );
            }
            int numArgs = ( templateArguments != null ) ? templateArguments.length : 0;
            
            
            if( name.getParent() instanceof IASTName )
                  name = (IASTName) name.getParent();
            IASTNode n = name.getParent();
            if( n instanceof ICPPASTQualifiedName ){
                  n = n.getParent();
            }
            ICPPASTFunctionDeclarator fdtor = (ICPPASTFunctionDeclarator) n;
            IType [] functionParameters = createTypeArray( fdtor.getParameters() );
            
            ICPPFunctionTemplate result = null;
            outer: for( int i = 0; i < templates.length && templates[i] != null; i++ ){
                  ICPPFunctionTemplate tmpl = templates[i];
                  
                  ObjectMap map = ObjectMap.EMPTY_MAP;
                  try {
                        map = deduceTemplateArguments( tmpl, functionParameters );
                  } catch (DOMException e) {
                  }
                  
                  if( map == null )
                        continue;                
                  ICPPTemplateParameter [] params = null;
                  try {
                        params = tmpl.getTemplateParameters();
                  } catch (DOMException e) {
                        continue;
                  }
                  
                  int numParams = params.length;
                  IType arg = null;
                  for( int j = 0; j < numParams; j++ ){
                        ICPPTemplateParameter param = params[j];
                        if( j < numArgs ){
                              arg = templateArguments[j];
                        } else
                              arg = null;
                        if( map.containsKey( param ) ) {
                              IType t = (IType) map.get( param );
                              if( arg == null ) 
                                    arg = t;
                              else if( !t.isSameType( arg ) ){
                                    continue outer;
                              }
                        } else if( arg == null || !matchTemplateParameterAndArgument( param, arg, map )){
                              continue outer;
                        }
                  }
                  //made it this far, its a match
                  if( result != null ){
                        return new CPPFunctionTemplate.CPPFunctionTemplateProblem(name, IProblemBinding.SEMANTIC_AMBIGUOUS_LOOKUP, name.toCharArray() );
                  } 
                  result = tmpl;
            }
            
            return result;
      }
      
      /**
       * return Object[] of { ObjectMap, IType[] } 
       * @param primaryTemplate
       * @param ps
       * @param specArgs
       * @return
       * @throws DOMException
       */
00531       static protected Object[] deduceTemplateFunctionArguments( ICPPFunctionTemplate primaryTemplate, IASTParameterDeclaration [] ps, IASTNode [] specArgs ) throws DOMException
      {
            ICPPTemplateParameter [] templateParameters = primaryTemplate.getTemplateParameters();
            IType [] arguments = createTypeArray( specArgs );
            IType [] result = new IType[ templateParameters.length ];
            
            ObjectMap map = null;
            
            if( arguments.length == result.length ){
                  map = new ObjectMap( result.length );
                  for (int i = 0; i < templateParameters.length; i++) {
                        result[i] = arguments[i];
                        map.put( templateParameters, arguments[i] );
                  }
                  return new Object[] { map, result };
            }
                  
            //else need to deduce some arguments
            IType [] paramTypes = createTypeArray( ps );
            map = deduceTemplateArguments( primaryTemplate, paramTypes );
            if( map != null ){
                  for( int i = 0; i < templateParameters.length; i++ ){
                        ICPPTemplateParameter param = templateParameters[i];
                        IType arg = null;
                        if( i < arguments.length ){
                              arg = arguments[i];
                              map.put( param, arg );
                        } else if( map.containsKey( param ) ){
                              arg = (IType) map.get( param );
                        }
                        
                        if( arg == null || !matchTemplateParameterAndArgument( param, arg, map ) )
                              return null;
                        
                        result[i] = arg;
                  }
                  return new Object[] { map, result };
            }
            
            return null;
      }

      /**
       * @param decl
       * @param arguments
       * @return
       */
00578       public static IBinding createInstance( ICPPScope scope, IBinding decl, ObjectMap argMap, IType [] args ) {
            ICPPTemplateInstance instance = null;
            if( decl instanceof ICPPClassType ){
                  instance = new CPPClassInstance( scope, decl, argMap, args );
            } else if( decl instanceof ICPPMethod ) {
                  instance = new CPPMethodInstance( scope, decl, argMap, args );
            } else if( decl instanceof ICPPFunction ) {
                  instance = new CPPFunctionInstance( scope, decl, argMap, args );
            }
            return instance;
      }
      
      public static ICPPSpecialization createSpecialization( ICPPScope scope, IBinding decl, ObjectMap argMap ){
            ICPPSpecialization spec = null;
            if( decl instanceof ICPPClassTemplate ){
                  spec = new CPPClassTemplateSpecialization( decl, scope, argMap );
            } else if( decl instanceof ICPPClassType ){
                  spec = new CPPClassSpecialization( decl, scope, argMap );
            } else if( decl instanceof ICPPField ){
                  spec = new CPPFieldSpecialization( decl, scope, argMap );
            } else if( decl instanceof ICPPFunctionTemplate ){
                  if( decl instanceof ICPPConstructor )
                        spec = new CPPConstructorTemplateSpecialization( decl, scope, argMap );
                  else if( decl instanceof ICPPMethod )
                        spec = new CPPMethodTemplateSpecialization( decl, scope, argMap );
                  else
                        spec = new CPPFunctionTemplateSpecialization( decl, scope, argMap );
            } else if( decl instanceof ICPPConstructor ){
                  spec = new CPPConstructorSpecialization( decl, scope, argMap );
            } else if( decl instanceof ICPPMethod ) {
                  spec = new CPPMethodSpecialization( decl, scope, argMap );
            } else if( decl instanceof ICPPFunction ) {
                  spec = new CPPFunctionSpecialization( decl, scope, argMap );
            } else if( decl instanceof ITypedef ){
                spec = new CPPTypedefSpecialization( decl, scope, argMap );
            }
            return spec;
      }

      /**
       * @param type
       * @param arguments
       */
00621       public static IType instantiateType(IType type, ObjectMap argMap) {
            if( argMap == null )
                  return type;
            
            IType newType = type;
            IType temp = null;
            if( type instanceof IFunctionType ){
                  IType ret = null;
                  IType [] params = null;
                  try {
                        ret = instantiateType( ((IFunctionType) type).getReturnType(), argMap );
                        IType [] ps = ((IFunctionType) type).getParameterTypes();
                        params = new IType[ ps.length ];
                        for (int i = 0; i < params.length; i++) {
                              temp = instantiateType( ps[i], argMap );
                              params[i] = temp;
                        }
                  } catch (DOMException e) {
                  }
                  newType = new CPPFunctionType( ret, params, ((ICPPFunctionType)type).isConst(), ((ICPPFunctionType)type).isVolatile() );
            } else if( type instanceof ITypeContainer ){
                  try {
                        temp = ((ITypeContainer) type).getType();
                  } catch (DOMException e) {
                        return type;
                  }
                  newType = instantiateType( temp, argMap );
                  if( newType != temp ){
                        temp = (IType) type.clone();
                        ((ITypeContainer)temp).setType( newType );
                        newType = temp;
                  } else {
                        newType = type;
                  }
            } else if( type instanceof ICPPTemplateParameter && argMap.containsKey( type ) ){
                  newType = (IType) argMap.get( type );
            } else if( type instanceof CPPDeferredClassInstance ){
                  newType = ((CPPDeferredClassInstance)type).instantiate( argMap );
            } else if( type instanceof ICPPInternalUnknown ){
                IBinding binding;
            try {
                binding = ((ICPPInternalUnknown)type).resolveUnknown( argMap );
            } catch ( DOMException e ) {
                binding = e.getProblem();
            }
            if( binding instanceof IType )
                    newType = (IType) binding; 
            }
      
            return newType;
      }

      public static ICPPASTTemplateDeclaration getTemplateDeclaration( IASTName name ){
            if( name == null ) return null;
            
            IASTNode parent = name.getParent();
            while( parent instanceof IASTName ){
                parent = parent.getParent();
            }
            if( parent instanceof IASTDeclSpecifier ){
                parent = parent.getParent();
            } else {
                  while( parent instanceof IASTDeclarator ){
                      parent = parent.getParent();
                  }
            }
            if( parent instanceof IASTDeclaration && parent.getParent() instanceof ICPPASTTemplateDeclaration ){
                parent = parent.getParent();
            } else {
                  return null;
            }
            
            if( parent instanceof ICPPASTTemplateDeclaration ){
                ICPPASTTemplateDeclaration templateDecl = (ICPPASTTemplateDeclaration) parent;
                while( templateDecl.getParent() instanceof ICPPASTTemplateDeclaration )
                    templateDecl = (ICPPASTTemplateDeclaration) templateDecl.getParent();

                  IASTName [] ns = null;
                  if( name instanceof ICPPASTQualifiedName ){
                        ns = ((ICPPASTQualifiedName)name).getNames();
                        name = ns[ ns.length - 1 ];
                  } else if( name.getParent() instanceof ICPPASTQualifiedName ){
                        ns = ((ICPPASTQualifiedName)name.getParent()).getNames();
                  }
                  if( ns != null ){
                        IASTDeclaration currDecl = templateDecl;
                        for (int j = 0; j < ns.length; j++) {
                              if( ns[j] == name ){
                                    if( ns[j] instanceof ICPPASTTemplateId || j + 1 == ns.length ){
                                          if( currDecl instanceof ICPPASTTemplateDeclaration )
                                                return (ICPPASTTemplateDeclaration) currDecl;
                                          return null;
                                    }
                              }
                              if( ns[j] instanceof ICPPASTTemplateId ){
                                    if( currDecl instanceof ICPPASTTemplateDeclaration )
                                          currDecl = ((ICPPASTTemplateDeclaration) currDecl).getDeclaration();
                                    else
                                          return null; //??? this would imply bad ast or code
                              }
                        }
                  } else {
                        return templateDecl;
                  }
            }
            return  null;
      }
      
      public static IASTName getTemplateName( ICPPASTTemplateDeclaration templateDecl ){
          if( templateDecl == null ) return null;
            
          ICPPASTTemplateDeclaration decl = templateDecl;
            while( decl.getParent() instanceof ICPPASTTemplateDeclaration )
                decl = (ICPPASTTemplateDeclaration) decl.getParent(); 

            IASTDeclaration nestedDecl = templateDecl.getDeclaration();
            while( nestedDecl instanceof ICPPASTTemplateDeclaration ){
                  nestedDecl = ((ICPPASTTemplateDeclaration)nestedDecl).getDeclaration();
            }
            
            IASTName name = null;
            if( nestedDecl instanceof IASTSimpleDeclaration ){
                IASTSimpleDeclaration simple = (IASTSimpleDeclaration) nestedDecl;
                if( simple.getDeclarators().length == 1 ){
                        IASTDeclarator dtor = simple.getDeclarators()[0];
                        while( dtor.getNestedDeclarator() != null )
                              dtor = dtor.getNestedDeclarator();
                    name = dtor.getName();
                } else if( simple.getDeclarators().length == 0 ){
                    IASTDeclSpecifier spec = simple.getDeclSpecifier();
                    if( spec instanceof ICPPASTCompositeTypeSpecifier )
                        name = ((ICPPASTCompositeTypeSpecifier)spec).getName();
                    else if( spec instanceof ICPPASTElaboratedTypeSpecifier )
                        name = ((ICPPASTElaboratedTypeSpecifier)spec).getName();
                }
            } else if( nestedDecl instanceof IASTFunctionDefinition ){
                name = ((IASTFunctionDefinition)nestedDecl).getDeclarator().getName();
            }
            if( name != null ){
                if( name instanceof ICPPASTQualifiedName ){
                        IASTName [] ns = ((ICPPASTQualifiedName) name).getNames();
                        IASTDeclaration currDecl = decl;
                        for (int j = 0; j < ns.length; j++) {
                              if( ns[j] instanceof ICPPASTTemplateId || j + 1 == ns.length){
                                    if( currDecl == templateDecl )
                                          return ns[j];
                                    if( currDecl instanceof ICPPASTTemplateDeclaration )
                                          currDecl = ((ICPPASTTemplateDeclaration)currDecl).getDeclaration();
                                    else
                                          return null;
                              }
                        }
                } else {
                    return name;
                }
            }

            return  null;
      }
      
      private static class ClearBindingAction extends CPPASTVisitor {
            public ObjectSet bindings = null;
            public ClearBindingAction( ObjectSet bindings ) {
                  shouldVisitNames = true;
                  shouldVisitStatements = true;
                  this.bindings = bindings;
            }
            public int visit(IASTName name) {
                  if( name.getBinding() != null ){
                        IBinding binding = name.getBinding();
                        boolean clear = bindings.containsKey( name.getBinding() );
                        if( !clear && binding instanceof ICPPTemplateInstance ){
                              IType [] args = ((ICPPTemplateInstance)binding).getArguments();
                              for( int i = 0; i < args.length; i++ ){
                                    if( bindings.containsKey( args[i] ) ){
                                          clear = true;
                                          break;
                                    }
                              }
                        }
                        if( clear ){
                              if( binding instanceof ICPPInternalBinding )
                                    ((ICPPInternalBinding)binding).removeDeclaration( name );
                              name.setBinding( null );
                        }
                  }
                  return PROCESS_CONTINUE;
            }
            public int visit(IASTStatement statement) {
                  return PROCESS_SKIP;
            }
      }
      /**
       * @param definition
       * @param declarator
       * @return
       */
00818       public static boolean isSameTemplate(ICPPTemplateDefinition definition, IASTName name) {
            ICPPTemplateParameter [] defParams = null;
            try {
                  defParams = definition.getTemplateParameters();
            } catch (DOMException e1) {
                  return false;
            }
            ICPPASTTemplateDeclaration templateDecl = getTemplateDeclaration( name );
            if( templateDecl == null )
                  return false;
            
            ICPPASTTemplateParameter [] templateParams = templateDecl.getTemplateParameters();
            if( defParams.length != templateParams.length )
                  return false;
            
            ObjectSet bindingsToClear = null;
            for (int i = 0; i < templateParams.length; i++) {
                  IASTName tn = getTemplateParameterName( templateParams[i] );
                  if( tn.getBinding() != null )
                        return ( tn.getBinding() == defParams[i] );
                  if( bindingsToClear == null )
                        bindingsToClear = new ObjectSet( templateParams.length );
                  tn.setBinding( defParams[i] );
                  ((ICPPInternalBinding)defParams[i]).addDeclaration( tn );
                  bindingsToClear.put( defParams[i] );
            }
            
            boolean result = false;
            IASTNode parent = name.getParent();
            if( parent instanceof ICPPASTFunctionDeclarator ){
                  try {
                        IASTParameterDeclaration [] params = ((ICPPASTFunctionDeclarator)parent).getParameters();
                        IParameter [] ps = ((ICPPFunction)definition).getParameters();
                        if( ps.length == params.length ) {
                              int i = 0;
                              for(; i < ps.length; i++) {
                                    IType t1 = CPPVisitor.createType( params[i].getDeclarator() );
                                    IType t2 = ps[i].getType();
                                    if( ! t1.isSameType( t2 ) ){
                                          break;
                                    }
                              }
                              if( i == ps.length )
                                    result = true;
                        }
                  } catch (DOMException e) {
                  }
            } else if( parent instanceof IASTDeclSpecifier ){
                  if( name instanceof ICPPASTTemplateId ){
                        if( definition instanceof ICPPClassTemplatePartialSpecialization ){
                              ICPPClassTemplatePartialSpecialization spec = (ICPPClassTemplatePartialSpecialization) definition;
                              IASTNode [] args = ((ICPPASTTemplateId)name).getTemplateArguments();
                              IType [] specArgs = null;
                              try {
                                    specArgs = spec.getArguments();
                              } catch (DOMException e) {
                                    result = false;
                              }
                              if( specArgs != null && args.length == specArgs.length ){
                                    int i = 0;
                                    for (; i < args.length; i++) {
                                          IType t1 = specArgs[i];
                                          IType t2 = CPPVisitor.createType( args[i] );
                                          if( t1 != null && t2 != null && t1.isSameType( t2 ) )
                                                continue;
                                          break;
                                    }
                                    result = ( i == args.length );
                              }
                        }
                  } else {
                        result = CharArrayUtils.equals( definition.getNameCharArray(), name.toCharArray() );
                  }
            }
            
            if( bindingsToClear != null && !result ){
                  ClearBindingAction action = new ClearBindingAction( bindingsToClear );
                  templateDecl.accept( action );
            }
            
            return result;
      }
      
      static public IType [] createTypeArray( Object [] params ){
            if( params == null )
                  return IType.EMPTY_TYPE_ARRAY;
            
            if( params instanceof IType[] )
                  return (IType[]) params;
            
            IType [] result = new IType[ params.length ];
            for( int i = 0; i < params.length; i++ ) {
                if( params[i] instanceof IASTNode ){
                        result[i] = CPPVisitor.createType( (IASTNode) params[ i ] );
                  } else if( params[i] instanceof IParameter ){
                        try {
                              result[i] = ((IParameter)params[i]).getType();
                        } catch (DOMException e) {
                              result[i] = e.getProblem();
                        }
                  }
            }
            return result;
      }
      
      static protected IFunction[] selectTemplateFunctions( ObjectSet templates, Object[] functionArguments, IASTName name ) {//IASTNode[] templateArguments ){
            if( templates == null || templates.size() == 0 )
                  return null;
            
            IFunction [] instances = null;
            
            int size = templates.size();
            
            int numTemplateArgs = 0;
            IASTNode [] templateArguments = null;
            if( name instanceof ICPPASTTemplateId )   {
                  templateArguments = ((ICPPASTTemplateId)name).getTemplateArguments();
                  numTemplateArgs = templateArguments.length;
            }
            
            IType [] fnArgs = createTypeArray( functionArguments );
            
            outer: for( int idx = 0; idx < size; idx++ ){
                  ICPPFunctionTemplate template = (ICPPFunctionTemplate) templates.keyAt( idx );
                  
                  ObjectMap map = null;
                  try {
                        map = deduceTemplateArguments( template, fnArgs );
                  } catch (DOMException e) {
                        continue;
                  }
                  if( map == null )
                        continue;
                  
                  ICPPTemplateParameter [] templateParams = null;
                  try {
                        templateParams = template.getTemplateParameters();
                  } catch (DOMException e1) {
                        continue outer;
                  }
                  int numTemplateParams = templateParams.length;
                  
                  IType [] instanceArgs = null;
                  for( int i = 0; i < numTemplateParams; i++ ){
                        IType arg = ( i < numTemplateArgs ) ? CPPVisitor.createType( templateArguments[i] ) : null;
                        IType mapped = (IType) map.get( templateParams[i] );
                        
                        if( arg != null && mapped != null )
                              if( arg.isSameType( mapped ) )
                                    instanceArgs = (IType[]) ArrayUtil.append( IType.class, instanceArgs, arg );
                              else
                                    continue outer;
                        else if( arg == null && mapped == null ) {
                            IType def = null;
                            try {
                                  if( templateParams[i] instanceof ICPPTemplateTypeParameter ){
                              def = ((ICPPTemplateTypeParameter)templateParams[i]).getDefault();
                                  } else if( templateParams[i] instanceof ICPPTemplateTemplateParameter ){
                                      def = ((ICPPTemplateTemplateParameter)templateParams[i]).getDefault();
                                  } else if( templateParams[i] instanceof ICPPTemplateNonTypeParameter ){
                                      def = CPPVisitor.getExpressionType( ((ICPPTemplateNonTypeParameter)templateParams[i]).getDefault() );
                                  }
                            } catch ( DOMException e ) {
                                continue outer;
                            }
                            if( def != null ){
                                if( def instanceof ICPPTemplateParameter ){
                                    for ( int j = 0; j < i; j++ ) {
                                if( templateParams[j] == def ) {
                                    def = instanceArgs[j];
                                }
                            }
                                }
                                instanceArgs = (IType[]) ArrayUtil.append( IType.class, instanceArgs, def );
                            } else 
                                continue outer;
                        } else
                              instanceArgs = (IType[]) ArrayUtil.append( IType.class, instanceArgs, (arg != null) ? arg : mapped );
                  }
                  instanceArgs  = (IType[]) ArrayUtil.trim( IType.class, instanceArgs );
                  ICPPSpecialization temp = (ICPPSpecialization) ((ICPPInternalTemplate)template).instantiate( instanceArgs );
                  if( temp != null )
                        instances = (IFunction[]) ArrayUtil.append( IFunction.class, instances, temp );
            }
            
            return (IFunction[]) ArrayUtil.trim( IFunction.class, instances );
      }
      
      /**
       * 
       * @param template
       * @param args
       * @return
       * 
       * A type that is specified in terms of template parameters (P) is compared with an actual 
       * type (A), and an attempt is made to find template argument vaules that will make P, 
       * after substitution of the deduced values, compatible with A.
       * @throws DOMException
       */
01017       static private ObjectMap deduceTemplateArguments( ICPPFunctionTemplate template, IType[] arguments ) throws DOMException{
            ICPPFunction function = (ICPPFunction) template;
            IParameter [] functionParameters = null;
            try {
                  functionParameters = function.getParameters();
            } catch (DOMException e) {
                  return null;
            }
            if( arguments == null /*|| functionParameters.length != arguments.length*/ ){
                  return null;
            }
            
            int numParams = functionParameters.length;
            int numArgs = arguments.length;
            ObjectMap map = new ObjectMap(numParams);
            for( int i = 0; i < numArgs && i < numParams; i++ ){
                  if( !deduceTemplateArgument( map, functionParameters[i].getType(), arguments[i] ) ){
                        return null;
                  }
            }
            
            return map;             
      }
      
      /**
       * 14.8.2.1-2 If P is a cv-qualified type, the top level cv-qualifiers of P's type are ignored for type
       * deduction.  If P is a reference type, the type referred to by P is used for Type deduction.
       * @param pSymbol
       * @return
       */   
01047       static private IType getParameterTypeForDeduction( IType pType ){
            IType result = pType;
            try {
                  if( pType instanceof IQualifierType ){
                        result = ((IQualifierType)pType).getType();
                  } else if( pType instanceof ICPPReferenceType ){
                        result = ((ICPPReferenceType)pType).getType();
                  } else if( pType instanceof  CPPPointerType ){
                        result = ((CPPPointerType)pType).stripQualifiers();
                  }
            } catch ( DOMException e ){
                  result = e.getProblem();
            }
            return result;
      }
      
      /**
       * 14.8.2.1-2
       * if P is not a reference type
       * - If A is an array type, the pointer type produced by the array-to-pointer conversion is used instead
       * - If A is a function type, the pointer type produced by the function-to-pointer conversion is used instead
       * - If A is a cv-qualified type, the top level cv-qualifiers are ignored for type deduction 
       * @param aInfo
       * @return
       */
01072       static private IType getArgumentTypeForDeduction( IType aType, boolean pIsAReferenceType ) {
            if( aType instanceof ICPPReferenceType ){
                try {
                aType = ((ICPPReferenceType)aType).getType();
            } catch ( DOMException e ) {
            }
            }
            IType result = aType;
            if( !pIsAReferenceType ){
                  try {
                        if( aType instanceof IArrayType ){
                              result = new CPPPointerType( ((IArrayType)aType).getType() );
                        } else if( aType instanceof IFunctionType ){
                              result = new CPPPointerType( aType );
                        } else if( aType instanceof IQualifierType ){
                              result = ((IQualifierType)aType).getType();
                        } else if( aType instanceof CPPPointerType ){
                              result = ((CPPPointerType)aType).stripQualifiers();
                        }
                  } catch( DOMException e ){
                        result = e.getProblem();
                  }
            }
                  
            return result;
      }

      static private boolean expressionsEquivalent( IASTExpression p, IASTExpression a ){
            if( p == null )
                  return true;
            
            if( p instanceof IASTLiteralExpression && a instanceof IASTLiteralExpression ){
                  return p.toString().equals( a.toString () );
            }
            return false;
      }
      static protected boolean deduceTemplateArgument( ObjectMap map, IType p, IType a ) throws DOMException {
            boolean pIsAReferenceType = ( p instanceof ICPPReferenceType );
            p = getParameterTypeForDeduction( p );
            a = getArgumentTypeForDeduction( a, pIsAReferenceType );
            
            if( p instanceof IBasicType ) {
                  if( p.isSameType( a ) && a instanceof IBasicType ) {
                        return expressionsEquivalent( ((IBasicType)p).getValue(), ((IBasicType)a).getValue() );
                  }
            } else {
                  while( p != null ){
                        while( a instanceof ITypedef )
                              a = ((ITypedef)a).getType();
                        if( p instanceof IBasicType ){
                              return p.isSameType( a );
                        } else if( p instanceof ICPPPointerToMemberType ){
                              if( !(a instanceof ICPPPointerToMemberType ) )
                                    return false;
                              
                              if( !deduceTemplateArgument( map, ((ICPPPointerToMemberType)p).getMemberOfClass(), ((ICPPPointerToMemberType)a).getMemberOfClass() ) )
                                    return false;
                              
                              p = ((ICPPPointerToMemberType)p).getType();
                              p = ((ICPPPointerToMemberType)a).getType();
                        } else if( p instanceof IPointerType ){
                              if( !(a instanceof IPointerType) ){
                                    return false;
                              }
                              p = ((IPointerType) p).getType();
                              a = ((IPointerType) a).getType();
                        } else if ( p instanceof IQualifierType ){
                              if( !(a instanceof IQualifierType) )
                                    return false;
                              a = ((IQualifierType)a).getType(); //TODO a = strip qualifiers from p out of a
                              p = ((IQualifierType)p).getType();
                        } else if( p instanceof IFunctionType ){
                              if( !(a instanceof IFunctionType ) )
                                    return false;
                              if( !deduceTemplateArgument( map, ((IFunctionType)p).getReturnType(), ((IFunctionType)a).getReturnType() ) )
                                    return false;
                              IType [] pParams = ((IFunctionType)p).getParameterTypes();
                              IType [] aParams = ((IFunctionType)a).getParameterTypes();
                              if( pParams.length != aParams.length )
                                    return false;
                              for (int i = 0; i < pParams.length; i++) {
                                    if( !deduceTemplateArgument( map, pParams[i], aParams[i] ) ) 
                                          return false;
                              }
                              return true;
                        } else if( p instanceof ICPPTemplateParameter ){
                              if( map.containsKey( p ) ){
                                    IType current = (IType)map.get( p );
                                    return current.isSameType( a );
                              } 
                              if( a == null )
                                    return false;
                              map.put( p, a );
                              return true;
                        } else if( p instanceof ICPPTemplateInstance ){
                              if( !(a instanceof ICPPTemplateInstance ) )
                                    return false;
                              ICPPTemplateInstance pInst = (ICPPTemplateInstance) p;
                              ICPPTemplateInstance aInst = (ICPPTemplateInstance) a;

                              IType [] pArgs = createTypeArray( pInst.getArguments() );
                              ObjectMap aMap = aInst.getArgumentMap();
                              if( aMap != null && !(aInst.getTemplateDefinition() instanceof ICPPClassTemplatePartialSpecialization) ) {
                                    ICPPTemplateParameter [] aParams = aInst.getTemplateDefinition().getTemplateParameters();
                                    if( pArgs.length != aParams.length )
                                          return false;
                                    for (int i = 0; i < pArgs.length; i++) {
                                          IType t = (IType) aMap.get( aParams[i] );
                                          if( t == null || !deduceTemplateArgument( map, pArgs[i], t ) ) 
                                                return false;
                                    }
                              } else {
                                    IType [] aArgs = createTypeArray( aInst.getArguments() );
                                    if( aArgs.length != pArgs.length )
                                          return false;
                                    for (int i = 0; i < pArgs.length; i++) {
                                          if( !deduceTemplateArgument( map, pArgs[i], aArgs[i] ) ) 
                                                return false;
                                    }
                              }
                              return true;
                        } else {
                              return p.isSameType( a );
                        }
                  }
            }

            return false;
      }
      
      /**
       * transform a function template for use in partial ordering, as described in the
       * spec 14.5.5.2-3 
       * @param template
       * @return
       * -for each type template parameter, synthesize a unique type and substitute that for each
       * occurence of that parameter in the function parameter list
       * -for each non-type template parameter, synthesize a unique value of the appropriate type and
       * susbstitute that for each occurence of that parameter in the function parameter list
       * for each template template parameter, synthesize a unique class template and substitute that
       * for each occurence of that parameter in the function parameter list
       * @throws DOMException
       */

01216       static private IType [] createArgsForFunctionTemplateOrdering( ICPPFunctionTemplate template ) throws DOMException{
            ICPPTemplateParameter [] paramList = template.getTemplateParameters();
            int size = paramList.length;
            IType [] args = new IType [ size ];
            for( int i = 0; i < size; i++ ){
                  ICPPTemplateParameter param = paramList[i];
                  if( param instanceof ICPPTemplateNonTypeParameter ){
                        IType t = ((ICPPTemplateNonTypeParameter)param).getType();
                        if( t instanceof CPPBasicType ){
                              CPPASTLiteralExpression exp = new CPPASTLiteralExpression();
                              exp.setValue( String.valueOf( i ) );
                              CPPBasicType temp = (CPPBasicType) t.clone();
                              temp.setValue( exp );
                              args[i] = temp;
                        }
                  } else {
                        args[i] = new CPPBasicType( -1, 0 );
                  }
            }
            return args;
      }
      
      static protected int orderTemplateFunctions( ICPPFunctionTemplate f1, ICPPFunctionTemplate f2 ) throws DOMException {
            //Using the transformed parameter list, perform argument deduction against the other
            //function template
            IType [] args = createArgsForFunctionTemplateOrdering( f1 );
            ICPPFunction function = (ICPPFunction) ((ICPPInternalTemplate)f1).instantiate( args );
            
            ObjectMap m1 = null;
            if( function != null )
                  m1 = deduceTemplateArguments( f2, function.getType().getParameterTypes() );
            
            args = createArgsForFunctionTemplateOrdering( f2 );
            function = (ICPPFunction) ((ICPPInternalTemplate)f2).instantiate( args );
            
            ObjectMap m2 = null;
            if( function != null )
                  m2 = deduceTemplateArguments( f1, function.getType().getParameterTypes() );
            
            //The transformed  template is at least as specialized as the other iff the deduction
            //succeeds and the deduced parameter types are an exact match
            //A template is more specialized than another iff it is at least as specialized as the
            //other template and that template is not at least as specialized as the first.
            boolean d1 = ( m1 != null );
            boolean d2 = ( m2 != null );
            
            if( d1 && d2 || !d1 && !d2 )
                  return 0;
            else if( d1 && !d2 )
                  return 1;
            else 
                  return -1;
      }
      
      static protected ICPPTemplateDefinition matchTemplatePartialSpecialization( ICPPClassTemplate template, IType[] args ) throws DOMException{
            if( template == null ){
                  return null;
            }
            
            ICPPClassTemplatePartialSpecialization[] specializations = template.getPartialSpecializations();
            int size = ( specializations != null ) ? specializations.length : 0;
            if( size == 0 ){
                  return template;
            }
            
            ICPPClassTemplatePartialSpecialization bestMatch = null, spec = null;
            boolean bestMatchIsBest = true;
            IType[] specArgs = null;
            for( int i = 0; i < size; i++ ){
                  spec = specializations[i];
                  specArgs = spec.getArguments();
                  if( specArgs == null || specArgs.length != args.length ){
                        continue;
                  }
                  
                  int specArgsSize = specArgs.length;             
                  ObjectMap map = new ObjectMap(specArgsSize);
                  IType t1 = null, t2 = null;

                  boolean match = true;
                  for( int j = 0; j < specArgsSize; j++ ){
                        t1 = specArgs[j];
                        t2 = args[j];
                        
                        if( !deduceTemplateArgument( map, t1, t2 ) ){
                              match = false;
                              break;
                        }
                  }
                  if( match ){
                        int compare = orderSpecializations( bestMatch, spec );
                        if( compare == 0 ){
                              bestMatchIsBest = false; 
                        } else if( compare < 0 ) {
                              bestMatch = spec;
                              bestMatchIsBest = true;
                        }
                  }
            }
            
            //14.5.4.1 If none of the specializations is more specialized than all the other matchnig
            //specializations, then the use of the class template is ambiguous and the program is ill-formed.
            if( !bestMatchIsBest ){
                  //TODO problem
                  return new CPPTemplateDefinition.CPPTemplateProblem( null, IProblemBinding.SEMANTIC_AMBIGUOUS_LOOKUP, null);
            }
            
            return bestMatch;
      }
      
      /**
       * Compare spec1 to spec2.  Return > 0 if spec1 is more specialized, < 0 if spec2
       * is more specialized, = 0 otherwise.
       * @param spec1
       * @param spec2
       * @return
       * @throws DOMException
       */
01334       static private int orderSpecializations( ICPPClassTemplatePartialSpecialization spec1, ICPPClassTemplatePartialSpecialization spec2 ) throws DOMException {
            if( spec1 == null ){
                  return -1;  
            }
            
            //to order class template specializations, we need to transform them into function templates
            ICPPFunctionTemplate template1 = null, template2 = null;
            
            if( spec1 instanceof ICPPClassType ) {
                  template1 = classTemplateSpecializationToFunctionTemplate( spec1 );
                  template2 = classTemplateSpecializationToFunctionTemplate( spec2 );     
            } else if( spec1 instanceof ICPPFunction ) {
                  template1 = (ICPPFunctionTemplate) spec1;
                  template2 = (ICPPFunctionTemplate) spec2;
            }
            
            return orderTemplateFunctions( template1, template2);
      }
      
      public static final class CPPImplicitFunctionTemplate extends CPPFunctionTemplate {
            IParameter [] functionParameters = null;
            ICPPTemplateParameter [] templateParameters = null;
            /**
             * @param name
             */
            public CPPImplicitFunctionTemplate( ICPPTemplateParameter [] templateParameters, IParameter [] functionParameters) {
                  super( null );
                  this.functionParameters = functionParameters;
                  this.templateParameters = templateParameters;
            }
            public IParameter[] getParameters() {
                  return functionParameters; 
            }
            public ICPPTemplateParameter[] getTemplateParameters() {
                  return templateParameters;
            }
            public IScope getScope() {
                  return null;
            }
            public IFunctionType getType() {
                  if( type == null ){
                        type = CPPVisitor.createImplicitFunctionType( new CPPBasicType(IBasicType.t_void, 0 ), functionParameters );
                  }
                  return type;
            }
      }
      /**
       * transform the class template to a function template as described in the spec
       * 14.5.4.2-1
       * @param template
       * @return IParameterizedSymbol
       * the function template has the same template parameters as the partial specialization and
       * has a single function parameter whose type is a class template specialization with the template 
       * arguments of the partial specialization
       */
01389       static private ICPPFunctionTemplate classTemplateSpecializationToFunctionTemplate( ICPPClassTemplatePartialSpecialization specialization ) {
            if( !(specialization instanceof ICPPClassType) )
                  return null;

            ICPPTemplateDefinition template = specialization;
            IType [] args = null;
            try {
                  args = specialization.getArguments();
            } catch (DOMException e1) {
                  return null;
            }
            
            IType paramType = (IType) ((ICPPInternalTemplate)template).instantiate( args );
            IParameter [] functionParameters = new IParameter[] { new CPPParameter( paramType ) };
            
            try {
                  return new CPPImplicitFunctionTemplate( specialization.getTemplateParameters(), functionParameters );
            } catch (DOMException e) {
                  return null;
            }
      }
      
      static private boolean isValidArgument(ICPPTemplateParameter param, IType argument) {
            //TODO
            return true;      
      }
      static protected boolean matchTemplateParameterAndArgument( ICPPTemplateParameter param, IType argument, ObjectMap map ){
            if( !isValidArgument(param, argument) ){
                  return false;
            }
            if( param instanceof ICPPTemplateTypeParameter )
                  return true;
            else if( param instanceof ICPPTemplateTemplateParameter ){
                  if( !( argument instanceof ICPPTemplateDefinition ) )
                        return false;
                  
                  ICPPTemplateParameter [] pParams = null, aParams = null;
                  try {
                        pParams = ((ICPPTemplateTemplateParameter)param).getTemplateParameters();
                        aParams = ((ICPPTemplateDefinition)argument).getTemplateParameters();
                  } catch ( DOMException e ) {
                        return false;
                  }
                  

                  int size = pParams.length;
                  if( aParams.length != size){
                        return false;
                  }
                  
                  for( int i = 0; i < size; i++){
                        if( (pParams[i] instanceof ICPPTemplateTypeParameter && !(aParams[i] instanceof ICPPTemplateTypeParameter)) ||
                              (pParams[i] instanceof ICPPTemplateTemplateParameter && !(aParams[i] instanceof ICPPTemplateTemplateParameter)) ||
                              (pParams[i] instanceof ICPPTemplateNonTypeParameter && !(aParams[i] instanceof ICPPTemplateNonTypeParameter)) )
                        {
                              return false;
                        }
                  }
                  
                  return true;
            } else {
                  try {
                        IType pType = ((ICPPTemplateNonTypeParameter)param).getType();
                        if( map != null && pType != null && map.containsKey( pType ) ){
                              pType = (IType) map.get( pType );
                        }
                        Cost cost = CPPSemantics.checkStandardConversionSequence( argument, pType );
                              
                        if( cost == null || cost.rank == Cost.NO_MATCH_RANK ){
                              return false;
                        }
                  } catch( DOMException e ){
                        return false;
                  }
            }
            return true;
      }

      public static IBinding instantiateWithinClassTemplate( ICPPClassTemplate template ) throws DOMException {
            IType [] args = null;
            if( template instanceof ICPPClassTemplatePartialSpecialization ){
                  args = ((ICPPClassTemplatePartialSpecialization)template).getArguments();
            } else {
                  ICPPTemplateParameter [] templateParameters = template.getTemplateParameters();
                  args = new IType [ templateParameters.length ];
                  for (int i = 0; i < templateParameters.length; i++) {
                        if( templateParameters[i] instanceof IType ){
                              args[i] = (IType) templateParameters[i];
                        } else if( templateParameters[i] instanceof ICPPTemplateNonTypeParameter ){
                              args[i] = ((ICPPTemplateNonTypeParameter)templateParameters[i]).getType();
                        }
                  }
            }
            
            if( template instanceof CPPClassTemplate ){
                  return ((CPPClassTemplate)template).instantiate( args );
            }
            return template;
      }
      
      public static boolean typeContainsTemplateParameter( IType t ){
            if( t instanceof ICPPTemplateParameter )
                  return true;
            t = CPPSemantics.getUltimateType( t, false );
            return (t instanceof ICPPTemplateParameter);
      }
      
      public static IBinding instantiateTemplate( ICPPTemplateDefinition template, IType [] arguments, ObjectMap specializedArgs ){
            if( template == null ){
                  template = null;
            }
            
            ICPPTemplateParameter[] parameters = null;
            try {
                  parameters = template.getTemplateParameters();
            } catch (DOMException e1) {
                  return e1.getProblem();
            }
            
            int numParams = ( parameters != null ) ? parameters.length : 0;
            int numArgs = arguments.length;
            
            if( numParams == 0 ){
                  return null;                        
            }

            ObjectMap map = new ObjectMap( numParams );
            ICPPTemplateParameter param = null;
            IType arg = null;
            IType[] actualArgs = new IType[ numParams ];
            
            for( int i = 0; i < numParams; i++ ){
                  arg = null;
                  param = parameters[i];
                  
                  if( i < numArgs ){
                        arg = arguments[i];
                        //If the argument is a template parameter, we can't instantiate yet, defer for later
                        if( typeContainsTemplateParameter( arg ) ){
                              return ((ICPPInternalTemplate)template).deferredInstance( arguments );
                        }
                  } else {
                        IType defaultType = null;
                        try {
                              if( param instanceof ICPPTemplateTypeParameter )
                                    defaultType = ((ICPPTemplateTypeParameter)param).getDefault();
                              else if( param instanceof ICPPTemplateTemplateParameter )
                                    defaultType = ((ICPPTemplateTemplateParameter)param).getDefault();
                              else if( param instanceof ICPPTemplateNonTypeParameter )
                                    defaultType = CPPVisitor.getExpressionType( ((ICPPTemplateNonTypeParameter)param).getDefault() );
                        } catch (DOMException e) {
                              defaultType = e.getProblem();
                        }
                        if( defaultType != null ){
                              if( defaultType instanceof ICPPTemplateParameter ){
                                    if( map.containsKey( defaultType ) ){
                                          arg = (IType) map.get( defaultType );
                                    }
                              } else {
                                  arg = defaultType;
                              }
                        } else {
                              //TODO problem
                              return null;
                        }
                  }
                  
                  if( CPPTemplates.matchTemplateParameterAndArgument( param, arg, map ) ){
                        map.put( param, arg );
                        actualArgs[i] = arg;
                  } else {
                        //TODO problem
                        return null;
                  }
            }
            
            ICPPSpecialization instance = ((ICPPInternalTemplate)template).getInstance( actualArgs );
            if( instance != null ){
                  return instance;
            } 
            
            if( specializedArgs != null ){
                  for( int i = 0; i < specializedArgs.size(); i++ ){
                        map.put( specializedArgs.keyAt(i), specializedArgs.getAt(i) );
                  }
            }
            
            ICPPScope scope = null;
            try {
                  scope = (ICPPScope) template.getScope();
            } catch (DOMException e) {
                  return e.getProblem();
            }
            instance = (ICPPTemplateInstance) CPPTemplates.createInstance( scope, template, map, arguments );
            ((ICPPInternalTemplate)template).addSpecialization( arguments, instance );
      
            return instance;  
      }
}

Generated by  Doxygen 1.6.0   Back to index