~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

public IType[] InferTypeArguments(IList<ITypeParameter> typeParameters, IList<ResolveResult> arguments, IList<IType> parameterTypes, out bool success, IList<IType> classTypeArguments = null)

116

{

117

if (typeParameters == null)

118

throw new ArgumentNullException("typeParameters");

119

if (arguments == null)

120

throw new ArgumentNullException("arguments");

121

if (parameterTypes == null)

122

throw new ArgumentNullException("parameterTypes");

123

try {

124

this.typeParameters = new TP[typeParameters.Count];

125

for (int i = 0; i < this.typeParameters.Length; i++) {

126

if (i != typeParameters[i].Index)

127

throw new ArgumentException("Type parameter has wrong index");

128

if (typeParameters[i].OwnerType != EntityType.Method)

129

throw new ArgumentException("Type parameter must be owned by a method");

130

this.typeParameters[i] = new TP(typeParameters[i]);

131

}

132

this.parameterTypes = new IType[Math.Min(arguments.Count, parameterTypes.Count)];

133

this.arguments = new ResolveResult[this.parameterTypes.Length];

134

for (int i = 0; i < this.parameterTypes.Length; i++) {

135

if (arguments[i] == null || parameterTypes[i] == null)

136

throw new ArgumentNullException();

137

this.arguments[i] = arguments[i];

138

this.parameterTypes[i] = parameterTypes[i];

139

}

140

this.classTypeArguments = classTypeArguments;

141

Log.WriteLine("Type Inference");

142

Log.WriteLine(" Signature: M<" + string.Join<TP>(", ", this.typeParameters) + ">"

143

+ "(" + string.Join<IType>(", ", this.parameterTypes) + ")");

144

Log.WriteCollection(" Arguments: ", arguments);

145

Log.Indent();

146

147

PhaseOne();

148

success = PhaseTwo();

149

150

Log.Unindent();

151

Log.WriteLine(" Type inference finished " + (success ? "successfully" : "with errors") + ": " +

152

"M<" + string.Join(", ", this.typeParameters.Select(tp => tp.FixedTo ?? SpecialType.UnknownType)) + ">");

153

return this.typeParameters.Select(tp => tp.FixedTo ?? SpecialType.UnknownType).ToArray();

154

} finally {

155

Reset();

156

}

157

}

158

159

void Reset()

160

{

161

// clean up so that memory used by the operation can be garbage collected as soon as possible

162

this.typeParameters = null;

163

this.parameterTypes = null;

164

this.arguments = null;

165

this.dependencyMatrix = null;

166

this.classTypeArguments = null;

167

}

168

169

/// <summary>

170

/// Infers type arguments for the <paramref name="typeParameters"/> occurring in the <paramref name="targetType"/>

171

/// so that the resulting type (after substition) satisfies the given bounds.

172

/// </summary>

173

public IType[] InferTypeArgumentsFromBounds(IList<ITypeParameter> typeParameters, IType targetType, IList<IType> lowerBounds, IList<IType> upperBounds, out bool success)

174

{

175

if (typeParameters == null)

176

throw new ArgumentNullException("typeParameters");

177

if (targetType == null)

178

throw new ArgumentNullException("targetType");

179

if (lowerBounds == null)

180

throw new ArgumentNullException("lowerBounds");

181

if (upperBounds == null)

182

throw new ArgumentNullException("upperBounds");

183

this.typeParameters = new TP[typeParameters.Count];

184

for (int i = 0; i < this.typeParameters.Length; i++) {

185

if (i != typeParameters[i].Index)

186

throw new ArgumentException("Type parameter has wrong index");

187

this.typeParameters[i] = new TP(typeParameters[i]);

188

}

189

foreach (IType b in lowerBounds) {

190

MakeLowerBoundInference(b, targetType);

191

}

192

foreach (IType b in upperBounds) {

193

MakeUpperBoundInference(b, targetType);

194

}

195

IType[] result = new IType[this.typeParameters.Length];

196

success = true;

197

for (int i = 0; i < result.Length; i++) {

198

success &= Fix(this.typeParameters[i]);

199

result[i] = this.typeParameters[i].FixedTo ?? SpecialType.UnknownType;

200

}

201

Reset();

202

return result;

203

}

204

#endregion

205

206

sealed class TP

207

{

208

public readonly HashSet<IType> LowerBounds = new HashSet<IType>();

209

public readonly HashSet<IType> UpperBounds = new HashSet<IType>();

210

public readonly ITypeParameter TypeParameter;

211

public IType FixedTo;

212

213

public bool IsFixed {

214

get { return FixedTo != null; }

215

}

216

217

public bool HasBounds {

218

get { return LowerBounds.Count > 0 || UpperBounds.Count > 0; }

219

}

220

221

public TP(ITypeParameter typeParameter)

222

{

223

if (typeParameter == null)

224

throw new ArgumentNullException("typeParameter");

225

this.TypeParameter = typeParameter;

226

}

227

228

public override string ToString()

229

{

230

return TypeParameter.Name;

231

}

232

}

233

234

sealed class OccursInVisitor : TypeVisitor

235

{

236

readonly TP[] tp;

237

public readonly bool[] Occurs;

238

239

public OccursInVisitor(TypeInference typeInference)

240

{

241

this.tp = typeInference.typeParameters;

242

this.Occurs = new bool[tp.Length];

243

}

244

245

public override IType VisitTypeParameter(ITypeParameter type)

246

{

247

int index = type.Index;

248

if (index < tp.Length && tp[index].TypeParameter == type)

249

Occurs[index] = true;

250

return base.VisitTypeParameter(type);

251

}

252

}

253

254

#region Inference Phases

255

void PhaseOne()

256

{

257

// C# 4.0 spec: §7.5.2.1 The first phase

258

Log.WriteLine("Phase One");

259

for (int i = 0; i < arguments.Length; i++) {

260

ResolveResult Ei = arguments[i];

261

IType Ti = parameterTypes[i];

262

263

LambdaResolveResult lrr = Ei as LambdaResolveResult;

264

if (lrr != null) {

265

MakeExplicitParameterTypeInference(lrr, Ti);

266

}

267

if (lrr != null || Ei is MethodGroupResolveResult) {

268

// this is not in the spec???

269

if (OutputTypeContainsUnfixed(Ei, Ti) && !InputTypesContainsUnfixed(Ei, Ti)) {

270

MakeOutputTypeInference(Ei, Ti);

271

}

272

}

273

274

if (IsValidType(Ei.Type)) {

275

if (Ti is ByReferenceType) {

276

MakeExactInference(Ei.Type, Ti);

277

} else {

278

MakeLowerBoundInference(Ei.Type, Ti);

279

}

280

}

281

}

282

}

283

284

static bool IsValidType(IType type)

285

{

286

return type.Kind != TypeKind.Unknown && type.Kind != TypeKind.Null;

287

}

288

289

bool PhaseTwo()

290

{

291

// C# 4.0 spec: §7.5.2.2 The second phase

292

Log.WriteLine("Phase Two");

293

// All unfixed type variables Xi which do not depend on any Xj are fixed.

294

List<TP> typeParametersToFix = new List<TP>();

295

foreach (TP Xi in typeParameters) {

296

if (Xi.IsFixed == false) {

297

if (!typeParameters.Any((TP Xj) => !Xj.IsFixed && DependsOn(Xi, Xj))) {

298

typeParametersToFix.Add(Xi);

299

}

300

}

301

}

302

// If no such type variables exist, all unfixed type variables Xi are fixed for which all of the following hold:

303

if (typeParametersToFix.Count == 0) {

304

Log.WriteLine("Type parameters cannot be fixed due to dependency cycles");

305

Log.WriteLine("Trying to break the cycle by fixing any TPs that have non-empty bounds...");

306

foreach (TP Xi in typeParameters) {

307

// Xi has a nonempty set of bounds

308

if (!Xi.IsFixed && Xi.HasBounds) {

309

// There is at least one type variable Xj that depends on Xi

310

if (typeParameters.Any((TP Xj) => DependsOn(Xj, Xi))) {

311

typeParametersToFix.Add(Xi);

312

}

313

}

314

}

315

}

316

// now fix 'em

317

bool errorDuringFix = false;

318

foreach (TP tp in typeParametersToFix) {

319

if (!Fix(tp))

320

errorDuringFix = true;

321

}

322

if (errorDuringFix)

323

return false;

324

bool unfixedTypeVariablesExist = typeParameters.Any((TP X) => X.IsFixed == false);

325

if (typeParametersToFix.Count == 0 && unfixedTypeVariablesExist) {

326

// If no such type variables exist and there are still unfixed type variables, type inference fails.

327

Log.WriteLine("Type inference fails: there are still unfixed TPs remaining");

328

return false;

329

} else if (!unfixedTypeVariablesExist) {

330

// Otherwise, if no further unfixed type variables exist, type inference succeeds.

331

return true;

332

} else {

333

// Otherwise, for all arguments ei with corresponding parameter type Ti

334

for (int i = 0; i < arguments.Length; i++) {

335

ResolveResult Ei = arguments[i];

336

IType Ti = parameterTypes[i];

337

// where the output types (§7.4.2.4) contain unfixed type variables Xj

338

// but the input types (§7.4.2.3) do not

339

if (OutputTypeContainsUnfixed(Ei, Ti) && !InputTypesContainsUnfixed(Ei, Ti)) {

340

// an output type inference (§7.4.2.6) is made for ei with type Ti.

341

Log.WriteLine("MakeOutputTypeInference for argument #" + i);

342

MakeOutputTypeInference(Ei, Ti);

343

}

344

}

345

// Then the second phase is repeated.

346

return PhaseTwo();

347

}

348

}

349

#endregion

350

351

#region Input Types / Output Types (§7.5.2.3 + §7.5.2.4)

352

static readonly IType[] emptyTypeArray = new IType[0];

353

354

IType[] InputTypes(ResolveResult e, IType t)

355

{

356

// C# 4.0 spec: §7.5.2.3 Input types

357

LambdaResolveResult lrr = e as LambdaResolveResult;

358

if (lrr != null && lrr.IsImplicitlyTyped || e is MethodGroupResolveResult) {

359

IMethod m = GetDelegateOrExpressionTreeSignature(t);

360

if (m != null) {

361

IType[] inputTypes = new IType[m.Parameters.Count];

362

for (int i = 0; i < inputTypes.Length; i++) {

363

inputTypes[i] = m.Parameters[i].Type;

364

}

365

return inputTypes;

366

}

367

}

368

return emptyTypeArray;

369

}

370

371

IType[] OutputTypes(ResolveResult e, IType t)

372

{

373

// C# 4.0 spec: §7.5.2.4 Output types

374

LambdaResolveResult lrr = e as LambdaResolveResult;

375

if (lrr != null || e is MethodGroupResolveResult) {

376

IMethod m = GetDelegateOrExpressionTreeSignature(t);

377

if (m != null) {

378

return new[] { m.ReturnType };

379

}

380

}

381

return emptyTypeArray;

382

}

383

384

static IMethod GetDelegateOrExpressionTreeSignature(IType t)

385

{

386

ParameterizedType pt = t as ParameterizedType;

387

if (pt != null && pt.TypeParameterCount == 1 && pt.Name == "Expression"

388

&& pt.Namespace == "System.Linq.Expressions")

389

{

390

t = pt.GetTypeArgument(0);

391

}

392

return t.GetDelegateInvokeMethod();

393

}

394

395

bool InputTypesContainsUnfixed(ResolveResult argument, IType parameterType)

396

{

397

return AnyTypeContainsUnfixedParameter(InputTypes(argument, parameterType));

398

}

399

400

bool OutputTypeContainsUnfixed(ResolveResult argument, IType parameterType)

401

{

402

return AnyTypeContainsUnfixedParameter(OutputTypes(argument, parameterType));

403

}

404

405

bool AnyTypeContainsUnfixedParameter(IEnumerable<IType> types)

406

{

407

OccursInVisitor o = new OccursInVisitor(this);

408

foreach (var type in types) {

409

type.AcceptVisitor(o);

410

}

411

for (int i = 0; i < typeParameters.Length; i++) {

412

if (!typeParameters[i].IsFixed && o.Occurs[i])

413

return true;

414

}

415

return false;

416

}

417

#endregion

418

419

#region DependsOn (§7.5.2.5)

420

// C# 4.0 spec: §7.5.2.5 Dependance

421

422

void CalculateDependencyMatrix()

423

{

424

int n = typeParameters.Length;

425

dependencyMatrix = new bool[n, n];

426

for (int k = 0; k < arguments.Length; k++) {

427

OccursInVisitor input = new OccursInVisitor(this);

428

OccursInVisitor output = new OccursInVisitor(this);

429

foreach (var type in InputTypes(arguments[k], parameterTypes[k])) {

430

type.AcceptVisitor(input);

431

}

432

foreach (var type in OutputTypes(arguments[k], parameterTypes[k])) {

433

type.AcceptVisitor(output);

434

}

435

for (int i = 0; i < n; i++) {

436

for (int j = 0; j < n; j++) {

437

dependencyMatrix[i, j] |= input.Occurs[j] && output.Occurs[i];

438

}

439

}

440

}

441

// calculate transitive closure using Warshall's algorithm:

442

for (int i = 0; i < n; i++) {

443

for (int j = 0; j < n; j++) {

444

if (dependencyMatrix[i, j]) {

445

for (int k = 0; k < n; k++) {

446

if (dependencyMatrix[j, k])

447

dependencyMatrix[i, k] = true;

448

}

449

}

450

}

451

}

452

}

453

454

bool DependsOn(TP x, TP y)

455

{

456

if (dependencyMatrix == null)

457

CalculateDependencyMatrix();

458

// x depends on y

459

return dependencyMatrix[x.TypeParameter.Index, y.TypeParameter.Index];

460

}

461

#endregion

462

463

#region MakeOutputTypeInference (§7.5.2.6)

464

void MakeOutputTypeInference(ResolveResult e, IType t)

465

{

466

Log.WriteLine(" MakeOutputTypeInference from " + e + " to " + t);

467

// If E is an anonymous function with inferred return type U (§7.5.2.12) and T is a delegate type or expression

468

// tree type with return type Tb, then a lower-bound inference (§7.5.2.9) is made from U to Tb.

469

LambdaResolveResult lrr = e as LambdaResolveResult;

470

if (lrr != null) {

471

IMethod m = GetDelegateOrExpressionTreeSignature(t);

472

if (m != null) {

473

IType inferredReturnType;

474

if (lrr.IsImplicitlyTyped) {

475

if (m.Parameters.Count != lrr.Parameters.Count)

476

return; // cannot infer due to mismatched parameter lists

477

TypeParameterSubstitution substitution = GetSubstitutionForFixedTPs();

478

IType[] inferredParameterTypes = new IType[m.Parameters.Count];

479

for (int i = 0; i < inferredParameterTypes.Length; i++) {

480

IType parameterType = m.Parameters[i].Type;

481

inferredParameterTypes[i] = parameterType.AcceptVisitor(substitution);

482

}

483

inferredReturnType = lrr.GetInferredReturnType(inferredParameterTypes);

484

} else {

485

inferredReturnType = lrr.GetInferredReturnType(null);

486

}

487

MakeLowerBoundInference(inferredReturnType, m.ReturnType);

488

return;

489

}

490

}

491

// Otherwise, if E is a method group and T is a delegate type or expression tree type

492

// with parameter types T1…Tk and return type Tb, and overload resolution

493

// of E with the types T1…Tk yields a single method with return type U, then a lower-bound

494

// inference is made from U to Tb.

495

MethodGroupResolveResult mgrr = e as MethodGroupResolveResult;

496

if (mgrr != null) {

497

IMethod m = GetDelegateOrExpressionTreeSignature(t);

498

if (m != null) {

499

ResolveResult[] args = new ResolveResult[m.Parameters.Count];

500

TypeParameterSubstitution substitution = GetSubstitutionForFixedTPs();

501

for (int i = 0; i < args.Length; i++) {

502

IParameter param = m.Parameters[i];

503

IType parameterType = param.Type.AcceptVisitor(substitution);

504

if ((param.IsRef || param.IsOut) && parameterType.Kind == TypeKind.ByReference) {

505

parameterType = ((ByReferenceType)parameterType).ElementType;

506

args[i] = new ByReferenceResolveResult(parameterType, param.IsOut);

507

} else {

508

args[i] = new ResolveResult(parameterType);

509

}

510

}

511

var or = mgrr.PerformOverloadResolution(compilation,

512

args,

513

allowExtensionMethods: false,

514

allowExpandingParams: false);

515

if (or.FoundApplicableCandidate && or.BestCandidateAmbiguousWith == null) {

516

IType returnType = or.GetBestCandidateWithSubstitutedTypeArguments().ReturnType;

517

MakeLowerBoundInference(returnType, m.ReturnType);

518

}

519

}

520

return;

521

}

522

// Otherwise, if E is an expression with type U, then a lower-bound inference is made from U to T.

523

if (IsValidType(e.Type)) {

524

MakeLowerBoundInference(e.Type, t);

525

}

526

}

527

528

TypeParameterSubstitution GetSubstitutionForFixedTPs()

529

{

530

IType[] fixedTypes = new IType[typeParameters.Length];

531

for (int i = 0; i < fixedTypes.Length; i++) {

532

fixedTypes[i] = typeParameters[i].FixedTo ?? SpecialType.UnknownType;

533

}

534

return new TypeParameterSubstitution(classTypeArguments, fixedTypes);

535

}

536

#endregion

537

538

#region MakeExplicitParameterTypeInference (§7.5.2.7)

539

void MakeExplicitParameterTypeInference(LambdaResolveResult e, IType t)

540

{

541

// C# 4.0 spec: §7.5.2.7 Explicit parameter type inferences

542

if (e.IsImplicitlyTyped || !e.HasParameterList)

543

return;

544

Log.WriteLine(" MakeExplicitParameterTypeInference from " + e + " to " + t);

545

IMethod m = GetDelegateOrExpressionTreeSignature(t);

546

if (m == null)

547

return;

548

for (int i = 0; i < e.Parameters.Count && i < m.Parameters.Count; i++) {

549

MakeExactInference(e.Parameters[i].Type, m.Parameters[i].Type);

550

}

551

}

552

#endregion

553

554

#region MakeExactInference (§7.5.2.8)

555

/// <summary>

556

/// Make exact inference from U to V.

557

/// C# 4.0 spec: §7.5.2.8 Exact inferences

558

/// </summary>

559

void MakeExactInference(IType U, IType V)

560

{

561

Log.WriteLine("MakeExactInference from " + U + " to " + V);

562

563

// If V is one of the unfixed Xi then U is added to the set of bounds for Xi.

564

TP tp = GetTPForType(V);

565

if (tp != null && tp.IsFixed == false) {

566

Log.WriteLine(" Add exact bound '" + U + "' to " + tp);

567

tp.LowerBounds.Add(U);

568

tp.UpperBounds.Add(U);

569

return;

570

}

571

// Handle by reference types:

572

ByReferenceType brU = U as ByReferenceType;

573

ByReferenceType brV = V as ByReferenceType;

574

if (brU != null && brV != null) {

575

MakeExactInference(brU.ElementType, brV.ElementType);

576

return;

577

}

578

// Handle array types:

579

ArrayType arrU = U as ArrayType;

580

ArrayType arrV = V as ArrayType;

581

if (arrU != null && arrV != null && arrU.Dimensions == arrV.Dimensions) {

582

MakeExactInference(arrU.ElementType, arrV.ElementType);

583

return;

584

}

585

// Handle parameterized type:

586

ParameterizedType pU = U as ParameterizedType;

587

ParameterizedType pV = V as ParameterizedType;

588

if (pU != null && pV != null

589

&& object.Equals(pU.GetDefinition(), pV.GetDefinition())

590

&& pU.TypeParameterCount == pV.TypeParameterCount)

591

{

592

Log.Indent();

593

for (int i = 0; i < pU.TypeParameterCount; i++) {

594

MakeExactInference(pU.GetTypeArgument(i), pV.GetTypeArgument(i));

595

}

596

Log.Unindent();

597

}

598

}

599

600

TP GetTPForType(IType v)

601

{

602

ITypeParameter p = v as ITypeParameter;

603

if (p != null) {

604

int index = p.Index;

605

if (index < typeParameters.Length && typeParameters[index].TypeParameter == p)

606

return typeParameters[index];

607

}

608

return null;

609

}

610

#endregion

611

612

#region MakeLowerBoundInference (§7.5.2.9)

613

/// <summary>

614

/// Make lower bound inference from U to V.

615

/// C# 4.0 spec: §7.5.2.9 Lower-bound inferences

616

/// </summary>

617

void MakeLowerBoundInference(IType U, IType V)

618

{

619

Log.WriteLine(" MakeLowerBoundInference from " + U + " to " + V);

620

621

// If V is one of the unfixed Xi then U is added to the set of bounds for Xi.

622

TP tp = GetTPForType(V);

623

if (tp != null && tp.IsFixed == false) {

624

Log.WriteLine(" Add lower bound '" + U + "' to " + tp);

625

tp.LowerBounds.Add(U);

626

return;

627

}

628

629

// Handle array types:

630

ArrayType arrU = U as ArrayType;

631

ArrayType arrV = V as ArrayType;

632

ParameterizedType pV = V as ParameterizedType;

633

if (arrU != null && arrV != null && arrU.Dimensions == arrV.Dimensions) {

634

MakeLowerBoundInference(arrU.ElementType, arrV.ElementType);

635

return;

636

} else if (arrU != null && IsGenericInterfaceImplementedByArray(pV) && arrU.Dimensions == 1) {

637

MakeLowerBoundInference(arrU.ElementType, pV.GetTypeArgument(0));

638

return;

639

}

640

// Handle parameterized types:

641

if (pV != null) {

642

ParameterizedType uniqueBaseType = null;

643

foreach (IType baseU in U.GetAllBaseTypes()) {

644

ParameterizedType pU = baseU as ParameterizedType;

645

if (pU != null && object.Equals(pU.GetDefinition(), pV.GetDefinition()) && pU.TypeParameterCount == pV.TypeParameterCount) {

646

if (uniqueBaseType == null)

647

uniqueBaseType = pU;

648

else

649

return; // cannot make an inference because it's not unique

650

}

651

}

652

Log.Indent();

653

if (uniqueBaseType != null) {

654

for (int i = 0; i < uniqueBaseType.TypeParameterCount; i++) {

655

IType Ui = uniqueBaseType.GetTypeArgument(i);

656

IType Vi = pV.GetTypeArgument(i);

657

if (Ui.IsReferenceType == true) {

658

// look for variance

659

ITypeParameter Xi = pV.GetDefinition().TypeParameters[i];

660

switch (Xi.Variance) {

661

case VarianceModifier.Covariant:

662

MakeLowerBoundInference(Ui, Vi);

663

break;

664

case VarianceModifier.Contravariant:

665

MakeUpperBoundInference(Ui, Vi);

666

break;

667

default: // invariant

668

MakeExactInference(Ui, Vi);

669

break;

670

}

671

} else {

672

// not known to be a reference type

673

MakeExactInference(Ui, Vi);

674

}

675

}

676

}

677

Log.Unindent();

678

}

679

}

680

681

static bool IsGenericInterfaceImplementedByArray(ParameterizedType rt)

682

{

683

if (rt == null || rt.TypeParameterCount != 1)

684

return false;

685

switch (rt.GetDefinition().FullName) {

686

case "System.Collections.Generic.IEnumerable":

687

case "System.Collections.Generic.ICollection":

688

case "System.Collections.Generic.IList":

689

case "System.Collections.Generic.IReadOnlyList":

690

return true;

691

default:

692

return false;

693

}

694

}

695

#endregion

696

697

#region MakeUpperBoundInference (§7.5.2.10)

698

/// <summary>

699

/// Make upper bound inference from U to V.

700

/// C# 4.0 spec: §7.5.2.10 Upper-bound inferences

701

/// </summary>

702

void MakeUpperBoundInference(IType U, IType V)

703

{

704

Log.WriteLine(" MakeUpperBoundInference from " + U + " to " + V);

705

706

// If V is one of the unfixed Xi then U is added to the set of bounds for Xi.

707

TP tp = GetTPForType(V);

708

if (tp != null && tp.IsFixed == false) {

709

Log.WriteLine(" Add upper bound '" + U + "' to " + tp);

710

tp.UpperBounds.Add(U);

711

return;

712

}

713

714

// Handle array types:

715

ArrayType arrU = U as ArrayType;

716

ArrayType arrV = V as ArrayType;

717

ParameterizedType pU = U as ParameterizedType;

718

if (arrV != null && arrU != null && arrU.Dimensions == arrV.Dimensions) {

719

MakeUpperBoundInference(arrU.ElementType, arrV.ElementType);

720

return;

721

} else if (arrV != null && IsGenericInterfaceImplementedByArray(pU) && arrV.Dimensions == 1) {

722

MakeUpperBoundInference(pU.GetTypeArgument(0), arrV.ElementType);

723

return;

724

}

725

// Handle parameterized types:

726

if (pU != null) {

727

ParameterizedType uniqueBaseType = null;

728

foreach (IType baseV in V.GetAllBaseTypes()) {

729

ParameterizedType pV = baseV as ParameterizedType;

730

if (pV != null && object.Equals(pU.GetDefinition(), pV.GetDefinition()) && pU.TypeParameterCount == pV.TypeParameterCount) {

731

if (uniqueBaseType == null)

732

uniqueBaseType = pV;

733

else

734

return; // cannot make an inference because it's not unique

735

}

736

}

737

Log.Indent();

738

if (uniqueBaseType != null) {

739

for (int i = 0; i < uniqueBaseType.TypeParameterCount; i++) {

740

IType Ui = pU.GetTypeArgument(i);

741

IType Vi = uniqueBaseType.GetTypeArgument(i);

742

if (Ui.IsReferenceType == true) {

743

// look for variance

744

ITypeParameter Xi = pU.GetDefinition().TypeParameters[i];

745

switch (Xi.Variance) {

746

case VarianceModifier.Covariant:

747

MakeUpperBoundInference(Ui, Vi);

748

break;

749

case VarianceModifier.Contravariant:

750

MakeLowerBoundInference(Ui, Vi);

751

break;

752

default: // invariant

753

MakeExactInference(Ui, Vi);

754

break;

755

}

756

} else {

757

// not known to be a reference type

758

MakeExactInference(Ui, Vi);

759

}

760

}

761

}

762

Log.Unindent();

763

}

764

}

765

#endregion

766

767

#region Fixing (§7.5.2.11)

768

bool Fix(TP tp)

769

{

770

Log.WriteLine(" Trying to fix " + tp);

771

Debug.Assert(!tp.IsFixed);

772

Log.Indent();

773

var types = CreateNestedInstance().FindTypesInBounds(tp.LowerBounds.ToArray(), tp.UpperBounds.ToArray());

774

Log.Unindent();

775

if (algorithm == TypeInferenceAlgorithm.ImprovedReturnAllResults) {

776

tp.FixedTo = IntersectionType.Create(types);

777

Log.WriteLine(" T was fixed " + (types.Count >= 1 ? "successfully" : "(with errors)") + " to " + tp.FixedTo);

778

return types.Count >= 1;

779

} else {

780

tp.FixedTo = GetFirstTypePreferNonInterfaces(types);

781

Log.WriteLine(" T was fixed " + (types.Count == 1 ? "successfully" : "(with errors)") + " to " + tp.FixedTo);

782

return types.Count == 1;

783

}

784

}

785

#endregion

786

787

#region Finding the best common type of a set of expresssions

788

/// <summary>

789

/// Gets the best common type (C# 4.0 spec: §7.5.2.14) of a set of expressions.

790

/// </summary>

791

public IType GetBestCommonType(IList<ResolveResult> expressions, out bool success)

792

{

793

if (expressions == null)

794

throw new ArgumentNullException("expressions");

795

if (expressions.Count == 1) {

796

success = (expressions[0].Type.Kind != TypeKind.Unknown);

797

return expressions[0].Type;

798

}

799

Log.WriteCollection("GetBestCommonType() for ", expressions);

800

try {

801

ITypeParameter tp = DummyTypeParameter.GetMethodTypeParameter(0);

802

this.typeParameters = new TP[1] { new TP(tp) };

803

foreach (ResolveResult r in expressions) {

804

MakeOutputTypeInference(r, tp);

805

}

806

success = Fix(typeParameters[0]);

807

return typeParameters[0].FixedTo ?? SpecialType.UnknownType;

808

} finally {

809

Reset();

810

}

811

}

812

#endregion

813

814

#region FindTypeInBounds

815

/// <summary>

816

/// Finds a type that satisfies the given lower and upper bounds.

817

/// </summary>

818

public IType FindTypeInBounds(IList<IType> lowerBounds, IList<IType> upperBounds)

819

{

820

if (lowerBounds == null)

821

throw new ArgumentNullException("lowerBounds");

822

if (upperBounds == null)

823

throw new ArgumentNullException("upperBounds");

824

825

IList<IType> result = FindTypesInBounds(lowerBounds, upperBounds);

826

827

if (algorithm == TypeInferenceAlgorithm.ImprovedReturnAllResults) {

828

return IntersectionType.Create(result);

829

} else {

830

// return any of the candidates (prefer non-interfaces)

831

return GetFirstTypePreferNonInterfaces(result);

832

}

833

}

834

835

static IType GetFirstTypePreferNonInterfaces(IList<IType> result)

836

{

837

return result.FirstOrDefault(c => c.Kind != TypeKind.Interface)

838

?? result.FirstOrDefault() ?? SpecialType.UnknownType;

839

}

840

841

IList<IType> FindTypesInBounds(IList<IType> lowerBounds, IList<IType> upperBounds)

842

{

843

// If there's only a single type; return that single type.

844

// If both inputs are empty, return the empty list.

845

if (lowerBounds.Count == 0 && upperBounds.Count <= 1)

846

return upperBounds;

847

if (upperBounds.Count == 0 && lowerBounds.Count <= 1)

848

return lowerBounds;

849

if (nestingLevel > maxNestingLevel)

850

return EmptyList<IType>.Instance;

851

852

// Finds a type X so that "LB <: X <: UB"

853

Log.WriteCollection("FindTypesInBound, LowerBounds=", lowerBounds);

854

Log.WriteCollection("FindTypesInBound, UpperBounds=", upperBounds);

855

856

// First try the Fixing algorithm from the C# spec (§7.5.2.11)

857

List<IType> candidateTypes = lowerBounds.Union(upperBounds)

858

.Where(c => lowerBounds.All(b => conversions.ImplicitConversion(b, c).IsValid))

859

.Where(c => upperBounds.All(b => conversions.ImplicitConversion(c, b).IsValid))

860

.ToList(); // evaluate the query only once

861

862

candidateTypes = candidateTypes.Where(

863

c => candidateTypes.All(o => conversions.ImplicitConversion(c, o).IsValid)

864

).ToList();

865

// If the specified algorithm produces a single candidate, we return

866

// that candidate.

867

// We also return the whole candidate list if we're not using the improved

868

// algorithm.

869

if (candidateTypes.Count == 1 || !(algorithm == TypeInferenceAlgorithm.Improved || algorithm == TypeInferenceAlgorithm.ImprovedReturnAllResults))

870

{

871

return candidateTypes;

872

}

873

candidateTypes.Clear();

874

875

// Now try the improved algorithm

876

Log.Indent();

877

List<ITypeDefinition> candidateTypeDefinitions;

878

if (lowerBounds.Count > 0) {

879

// Find candidates by using the lower bounds:

880

var hashSet = new HashSet<ITypeDefinition>(lowerBounds[0].GetAllBaseTypeDefinitions());

881

for (int i = 1; i < lowerBounds.Count; i++) {

882

hashSet.IntersectWith(lowerBounds[i].GetAllBaseTypeDefinitions());

883

}

884

candidateTypeDefinitions = hashSet.ToList();

885

} else {

886

// Find candidates by looking at all classes in the project:

887

candidateTypeDefinitions = compilation.GetAllTypeDefinitions().ToList();

888

}

889

890

// Now filter out candidates that violate the upper bounds:

891

foreach (IType ub in upperBounds) {

892

ITypeDefinition ubDef = ub.GetDefinition();

893

if (ubDef != null) {

894

candidateTypeDefinitions.RemoveAll(c => !c.IsDerivedFrom(ubDef));

895

}

896

}

897

898

foreach (ITypeDefinition candidateDef in candidateTypeDefinitions) {

899

// determine the type parameters for the candidate:

900

IType candidate;

901

if (candidateDef.TypeParameterCount == 0) {

902

candidate = candidateDef;

903

} else {

904

Log.WriteLine("Inferring arguments for candidate type definition: " + candidateDef);

905

bool success;

906

IType[] result = InferTypeArgumentsFromBounds(

907

candidateDef.TypeParameters,

908

new ParameterizedType(candidateDef, candidateDef.TypeParameters),

909

lowerBounds, upperBounds,

910

out success);

911

if (success) {

912

candidate = new ParameterizedType(candidateDef, result);

913

} else {

914

Log.WriteLine("Inference failed; ignoring candidate");

915

continue;

916

}

917

}

918

Log.WriteLine("Candidate type: " + candidate);

919

920

if (lowerBounds.Count > 0) {

921

// if there were lower bounds, we aim for the most specific candidate:

922

923

// if this candidate isn't made redundant by an existing, more specific candidate:

924

if (!candidateTypes.Any(c => c.GetDefinition().IsDerivedFrom(candidateDef))) {

925

// remove all existing candidates made redundant by this candidate:

926

candidateTypes.RemoveAll(c => candidateDef.IsDerivedFrom(c.GetDefinition()));

927

// add new candidate

928

candidateTypes.Add(candidate);

929

}

930

} else {

931

// if there only were upper bounds, we aim for the least specific candidate:

932

933

// if this candidate isn't made redundant by an existing, less specific candidate:

934

if (!candidateTypes.Any(c => candidateDef.IsDerivedFrom(c.GetDefinition()))) {

935

// remove all existing candidates made redundant by this candidate:

936

candidateTypes.RemoveAll(c => c.GetDefinition().IsDerivedFrom(candidateDef));

937

// add new candidate

938

candidateTypes.Add(candidate);

939

}

940

}

941

}

942

Log.Unindent();

943

return candidateTypes;

944

}

945

#endregion

946

}

947

}

Older »