test/Tizen.NUI.Devel.Tests.Ubuntu/nunit.framework/Internal/Builders/PairwiseStrategy.cs

   1 // ***********************************************************************
   2 // Copyright (c) 2008 Charlie Poole
   3 //
   4 // Permission is hereby granted, free of charge, to any person obtaining
   5 // a copy of this software and associated documentation files (the
   6 // "Software"), to deal in the Software without restriction, including
   7 // without limitation the rights to use, copy, modify, merge, publish,
   8 // distribute, sublicense, and/or sell copies of the Software, and to
   9 // permit persons to whom the Software is furnished to do so, subject to
  10 // the following conditions:
  11 //
  12 // The above copyright notice and this permission notice shall be
  13 // included in all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  19 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  20 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  21 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22 // ***********************************************************************
  23 #define PORTABLE
  24 #define TIZEN
  25 #define NUNIT_FRAMEWORK
  26 #define NUNITLITE
  27 #define NET_4_5
  28 #define PARALLEL
  29 using System;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32 using System.Text;
  33 using NUnit.Framework.Interfaces;
  34
  35 namespace NUnit.Framework.Internal.Builders
  36 {
  37     /// <summary>
  38     /// PairwiseStrategy creates test cases by combining the parameter
  39     /// data so that all possible pairs of data items are used.
  40     /// </summary>
  41     /// <remarks>
  42     /// <para>
  43     /// The number of test cases that cover all possible pairs of test function
  44     /// parameters values is significantly less than the number of test cases
  45     /// that cover all possible combination of test function parameters values.
  46     /// And because different studies show that most of software failures are
  47     /// caused by combination of no more than two parameters, pairwise testing
  48     /// can be an effective ways to test the system when it's impossible to test
  49     /// all combinations of parameters.
  50     /// </para>
  51     /// <para>
  52     /// The PairwiseStrategy code is based on "jenny" tool by Bob Jenkins:
  53     /// http://burtleburtle.net/bob/math/jenny.html
  54     /// </para>
  55     /// </remarks>
  56     public class PairwiseStrategy : ICombiningStrategy
  57     {
  58         // NOTE: Terminology in this class is based on the literature
  59         // relating to strategies for combining variable features when
  60         // creating tests. This terminology is more closely related to
  61         // higher level testing than it is to unit tests. See
  62         // comments in the code for further explanations.
  63
  64         #region Internals
  65
  66         /// <summary>
  67         /// FleaRand is a pseudo-random number generator developed by Bob Jenkins:
  68         /// http://burtleburtle.net/bob/rand/talksmall.html#flea
  69         /// </summary>
  70         internal class FleaRand
  71         {
  72             private uint _b;
  73             private uint _c;
  74             private uint _d;
  75             private uint _z;
  76             private uint[] _m;
  77             private uint[] _r;
  78             private uint _q;
  79
  80             /// <summary>
  81             /// Initializes a new instance of the FleaRand class.
  82             /// </summary>
  83             /// <param name="seed">The seed.</param>
  84             public FleaRand( uint seed )
  85             {
  86                 _b = seed;
  87                 _c = seed;
  88                 _d = seed;
  89                 _z = seed;
  90                 _m = new uint[256];
  91                 _r = new uint[256];
  92
  93                 for ( int i = 0; i < _m.Length; i++ )
  94                 {
  95                     _m[i] = seed;
  96                 }
  97
  98                 for ( int i = 0; i < 10; i++ )
  99                 {
 100                     Batch();
 101                 }
 102
 103                 _q = 0;
 104             }
 105
 106             public uint Next()
 107             {
 108                 if ( _q == 0 )
 109                 {
 110                     Batch();
 111                     _q = (uint)_r.Length - 1;
 112                 }
 113                 else
 114                 {
 115                     _q--;
 116                 }
 117
 118                 return _r[_q];
 119             }
 120
 121             private void Batch()
 122             {
 123                 uint a;
 124                 uint b = _b;
 125                 uint c = _c + ( ++_z );
 126                 uint d = _d;
 127
 128                 for ( int i = 0; i < _r.Length; i++ )
 129                 {
 130                     a = _m[b % _m.Length];
 131                     _m[b % _m.Length] = d;
 132                     d = ( c << 19 ) + ( c >> 13 ) + b;
 133                     c = b ^ _m[i];
 134                     b = a + d;
 135                     _r[i] = c;
 136                 }
 137
 138                 _b = b;
 139                 _c = c;
 140                 _d = d;
 141             }
 142         }
 143
 144         /// <summary>
 145         /// FeatureInfo represents coverage of a single value of test function
 146         /// parameter, represented as a pair of indices, Dimension and Feature. In
 147         /// terms of unit testing, Dimension is the index of the test parameter and
 148         /// Feature is the index of the supplied value in that parameter's list of
 149         /// sources.
 150         /// </summary>
 151         internal class FeatureInfo
 152         {
 153             public readonly int Dimension;
 154
 155             public readonly int Feature;
 156
 157             /// <summary>
 158             /// Initializes a new instance of FeatureInfo class.
 159             /// </summary>
 160             /// <param name="dimension">Index of a dimension.</param>
 161             /// <param name="feature">Index of a feature.</param>
 162             public FeatureInfo( int dimension, int feature )
 163             {
 164                 Dimension = dimension;
 165                 Feature = feature;
 166             }
 167         }
 168
 169         /// <summary>
 170         /// A FeatureTuple represents a combination of features, one per test
 171         /// parameter, which should be covered by a test case. In the
 172         /// PairwiseStrategy, we are only trying to cover pairs of features, so the
 173         /// tuples actually may contain only single feature or pair of features, but
 174         /// the algorithm itself works with triplets, quadruples and so on.
 175         /// </summary>
 176         internal class FeatureTuple
 177         {
 178             private readonly FeatureInfo[] _features;
 179
 180             /// <summary>
 181             /// Initializes a new instance of FeatureTuple class for a single feature.
 182             /// </summary>
 183             /// <param name="feature1">Single feature.</param>
 184             public FeatureTuple( FeatureInfo feature1 )
 185             {
 186                 _features = new FeatureInfo[] { feature1 };
 187             }
 188
 189             /// <summary>
 190             /// Initializes a new instance of FeatureTuple class for a pair of features.
 191             /// </summary>
 192             /// <param name="feature1">First feature.</param>
 193             /// <param name="feature2">Second feature.</param>
 194             public FeatureTuple( FeatureInfo feature1, FeatureInfo feature2 )
 195             {
 196                 _features = new FeatureInfo[] { feature1, feature2 };
 197             }
 198
 199             public int Length
 200             {
 201                 get
 202                 {
 203                     return _features.Length;
 204                 }
 205             }
 206
 207             public FeatureInfo this[int index]
 208             {
 209                 get
 210                 {
 211                     return _features[index];
 212                 }
 213             }
 214         }
 215
 216         /// <summary>
 217         /// TestCase represents a single test case covering a list of features.
 218         /// </summary>
 219         internal class TestCaseInfo
 220         {
 221             public readonly int[] Features;
 222
 223             /// <summary>
 224             /// Initializes a new instance of TestCaseInfo class.
 225             /// </summary>
 226             /// <param name="length">A number of features in the test case.</param>
 227             public TestCaseInfo( int length )
 228             {
 229                 Features = new int[length];
 230             }
 231
 232             public bool IsTupleCovered( FeatureTuple tuple )
 233             {
 234                 for ( int i = 0; i < tuple.Length; i++ )
 235                 {
 236                     if ( Features[tuple[i].Dimension] != tuple[i].Feature )
 237                     {
 238                         return false;
 239                     }
 240                 }
 241
 242                 return true;
 243             }
 244         }
 245
 246         /// <summary>
 247         /// PairwiseTestCaseGenerator class implements an algorithm which generates
 248         /// a set of test cases which covers all pairs of possible values of test
 249         /// function.
 250         /// </summary>
 251         /// <remarks>
 252         /// <para>
 253         /// The algorithm starts with creating a set of all feature tuples which we
 254         /// will try to cover (see <see
 255         /// cref="PairwiseTestCaseGenerator.CreateAllTuples" /> method). This set
 256         /// includes every single feature and all possible pairs of features. We
 257         /// store feature tuples in the 3-D collection (where axes are "dimension",
 258         /// "feature", and "all combinations which includes this feature"), and for
 259         /// every two feature (e.g. "A" and "B") we generate both ("A", "B") and
 260         /// ("B", "A") pairs. This data structure extremely reduces the amount of
 261         /// time needed to calculate coverage for a single test case (this
 262         /// calculation is the most time-consuming part of the algorithm).
 263         /// </para>
 264         /// <para>
 265         /// Then the algorithm picks one tuple from the uncovered tuple, creates a
 266         /// test case that covers this tuple, and then removes this tuple and all
 267         /// other tuples covered by this test case from the collection of uncovered
 268         /// tuples.
 269         /// </para>
 270         /// <para>
 271         /// Picking a tuple to cover
 272         /// </para>
 273         /// <para>
 274         /// There are no any special rules defined for picking tuples to cover. We
 275         /// just pick them one by one, in the order they were generated.
 276         /// </para>
 277         /// <para>
 278         /// Test generation
 279         /// </para>
 280         /// <para>
 281         /// Test generation starts from creating a completely random test case which
 282         /// covers, nevertheless, previously selected tuple. Then the algorithm
 283         /// tries to maximize number of tuples which this test covers.
 284         /// </para>
 285         /// <para>
 286         /// Test generation and maximization process repeats seven times for every
 287         /// selected tuple and then the algorithm picks the best test case ("seven"
 288         /// is a magic number which provides good results in acceptable time).
 289         /// </para>
 290         /// <para>Maximizing test coverage</para>
 291         /// <para>
 292         /// To maximize tests coverage, the algorithm walks thru the list of mutable
 293         /// dimensions (mutable dimension is a dimension that are not included in
 294         /// the previously selected tuple). Then for every dimension, the algorithm
 295         /// walks thru the list of features and checks if this feature provides
 296         /// better coverage than randomly selected feature, and if yes keeps this
 297         /// feature.
 298         /// </para>
 299         /// <para>
 300         /// This process repeats while it shows progress. If the last iteration
 301         /// doesn't improve coverage, the process ends.
 302         /// </para>
 303         /// <para>
 304         /// In addition, for better results, before start every iteration, the
 305         /// algorithm "scrambles" dimensions - so for every iteration dimension
 306         /// probes in a different order.
 307         /// </para>
 308         /// </remarks>
 309         internal class PairwiseTestCaseGenerator
 310         {
 311             private FleaRand _prng;
 312
 313             private int[] _dimensions;
 314
 315             private List<FeatureTuple>[][] _uncoveredTuples;
 316
 317             /// <summary>
 318             /// Creates a set of test cases for specified dimensions.
 319             /// </summary>
 320             /// <param name="dimensions">
 321             /// An array which contains information about dimensions. Each element of
 322             /// this array represents a number of features in the specific dimension.
 323             /// </param>
 324             /// <returns>
 325             /// A set of test cases.
 326             /// </returns>
 327             public IEnumerable GetTestCases( int[] dimensions )
 328             {
 329                 _prng = new FleaRand( 15485863 );
 330                 _dimensions = dimensions;
 331
 332                 CreateAllTuples();
 333
 334                 List<TestCaseInfo> testCases = new List<TestCaseInfo>();
 335
 336                 while ( true )
 337                 {
 338                     FeatureTuple tuple = GetNextTuple();
 339
 340                     if ( tuple == null )
 341                     {
 342                         break;
 343                     }
 344
 345                     TestCaseInfo testCase = CreateTestCase( tuple );
 346
 347                     RemoveTuplesCoveredByTest( testCase );
 348
 349                     testCases.Add( testCase );
 350                 }
 351
 352 #if DEBUG
 353                 SelfTest( testCases );
 354 #endif
 355
 356                 return testCases;
 357             }
 358
 359             private int GetNextRandomNumber()
 360             {
 361                 return (int)( _prng.Next() >> 1 );
 362             }
 363
 364             private void CreateAllTuples()
 365             {
 366                 _uncoveredTuples = new List<FeatureTuple>[_dimensions.Length][];
 367
 368                 for ( int d = 0; d < _dimensions.Length; d++ )
 369                 {
 370                     _uncoveredTuples[d] = new List<FeatureTuple>[_dimensions[d]];
 371
 372                     for ( int f = 0; f < _dimensions[d]; f++ )
 373                     {
 374                         _uncoveredTuples[d][f] = CreateTuples( d, f );
 375                     }
 376                 }
 377             }
 378
 379             private List<FeatureTuple> CreateTuples( int dimension, int feature )
 380             {
 381                 List<FeatureTuple> result = new List<FeatureTuple>();
 382
 383                 result.Add( new FeatureTuple( new FeatureInfo( dimension, feature ) ) );
 384
 385                 for ( int d = 0; d < _dimensions.Length; d++ )
 386                 {
 387                     if ( d != dimension )
 388                     {
 389                         for ( int f = 0; f < _dimensions[d]; f++ )
 390                         {
 391                             result.Add( new FeatureTuple( new FeatureInfo( dimension, feature ), new FeatureInfo( d, f ) ) );
 392                         }
 393                     }
 394                 }
 395
 396                 return result;
 397             }
 398
 399             private FeatureTuple GetNextTuple()
 400             {
 401                 for ( int d = 0; d < _uncoveredTuples.Length; d++ )
 402                 {
 403                     for ( int f = 0; f < _uncoveredTuples[d].Length; f++ )
 404                     {
 405                         List<FeatureTuple> tuples = _uncoveredTuples[d][f];
 406
 407                         if ( tuples.Count > 0 )
 408                         {
 409                             FeatureTuple tuple = tuples[0];
 410                             tuples.RemoveAt( 0 );
 411                             return tuple;
 412                         }
 413                     }
 414                 }
 415
 416                 return null;
 417             }
 418
 419             private TestCaseInfo CreateTestCase( FeatureTuple tuple )
 420             {
 421                 TestCaseInfo bestTestCase = null;
 422                 int bestCoverage = -1;
 423
 424                 for ( int i = 0; i < 7; i++ )
 425                 {
 426                     TestCaseInfo testCase = CreateRandomTestCase( tuple );
 427
 428                     int coverage = MaximizeCoverage( testCase, tuple );
 429
 430                     if ( coverage > bestCoverage )
 431                     {
 432                         bestTestCase = testCase;
 433                         bestCoverage = coverage;
 434                     }
 435                 }
 436
 437                 return bestTestCase;
 438             }
 439
 440             private TestCaseInfo CreateRandomTestCase( FeatureTuple tuple )
 441             {
 442                 TestCaseInfo result = new TestCaseInfo( _dimensions.Length );
 443
 444                 for ( int d = 0; d < _dimensions.Length; d++ )
 445                 {
 446                     result.Features[d] = GetNextRandomNumber() % _dimensions[d];
 447                 }
 448
 449                 for ( int i = 0; i < tuple.Length; i++ )
 450                 {
 451                     result.Features[tuple[i].Dimension] = tuple[i].Feature;
 452                 }
 453
 454                 return result;
 455             }
 456
 457             private int MaximizeCoverage( TestCaseInfo testCase, FeatureTuple tuple )
 458             {
 459                 // It starts with one because we always have one tuple which is covered by the test.
 460                 int totalCoverage = 1;
 461                 int[] mutableDimensions = GetMutableDimensions( tuple );
 462
 463                 while ( true )
 464                 {
 465                     bool progress = false;
 466
 467                     ScrambleDimensions( mutableDimensions );
 468
 469                     for ( int i = 0; i < mutableDimensions.Length; i++ )
 470                     {
 471                         int d = mutableDimensions[i];
 472
 473                         int bestCoverage = CountTuplesCoveredByTest( testCase, d, testCase.Features[d] );
 474
 475                         int newCoverage = MaximizeCoverageForDimension( testCase, d, bestCoverage );
 476
 477                         totalCoverage += newCoverage;
 478
 479                         if ( newCoverage > bestCoverage )
 480                         {
 481                             progress = true;
 482                         }
 483                     }
 484
 485                     if ( !progress )
 486                     {
 487                         return totalCoverage;
 488                     }
 489                 }
 490             }
 491
 492             private int[] GetMutableDimensions( FeatureTuple tuple )
 493             {
 494                 List<int> result = new List<int>();
 495
 496                 bool[] immutableDimensions = new bool[_dimensions.Length];
 497
 498                 for ( int i = 0; i < tuple.Length; i++ )
 499                 {
 500                     immutableDimensions[tuple[i].Dimension] = true;
 501                 }
 502
 503                 for ( int d = 0; d < _dimensions.Length; d++ )
 504                 {
 505                     if ( !immutableDimensions[d] )
 506                     {
 507                         result.Add( d );
 508                     }
 509                 }
 510
 511                 return result.ToArray();
 512             }
 513
 514             private void ScrambleDimensions( int[] dimensions )
 515             {
 516                 for ( int i = 0; i < dimensions.Length; i++ )
 517                 {
 518                     int j = GetNextRandomNumber() % dimensions.Length;
 519                     int t = dimensions[i];
 520                     dimensions[i] = dimensions[j];
 521                     dimensions[j] = t;
 522                 }
 523             }
 524
 525             private int MaximizeCoverageForDimension( TestCaseInfo testCase, int dimension, int bestCoverage )
 526             {
 527                 List<int> bestFeatures = new List<int>( _dimensions[dimension] );
 528
 529                 for ( int f = 0; f < _dimensions[dimension]; f++ )
 530                 {
 531                     testCase.Features[dimension] = f;
 532
 533                     int coverage = CountTuplesCoveredByTest( testCase, dimension, f );
 534
 535                     if ( coverage >= bestCoverage )
 536                     {
 537                         if ( coverage > bestCoverage )
 538                         {
 539                             bestCoverage = coverage;
 540                             bestFeatures.Clear();
 541                         }
 542
 543                         bestFeatures.Add( f );
 544                     }
 545                 }
 546
 547                 testCase.Features[dimension] = bestFeatures[GetNextRandomNumber() % bestFeatures.Count];
 548
 549                 return bestCoverage;
 550             }
 551
 552             private int CountTuplesCoveredByTest( TestCaseInfo testCase, int dimension, int feature )
 553             {
 554                 int result = 0;
 555
 556                 List<FeatureTuple> tuples = _uncoveredTuples[dimension][feature];
 557
 558                 for ( int i = 0; i < tuples.Count; i++ )
 559                 {
 560                     if ( testCase.IsTupleCovered( tuples[i] ) )
 561                     {
 562                         result++;
 563                     }
 564                 }
 565
 566                 return result;
 567             }
 568
 569             private void RemoveTuplesCoveredByTest( TestCaseInfo testCase )
 570             {
 571                 for ( int d = 0; d < _uncoveredTuples.Length; d++ )
 572                 {
 573                     for ( int f = 0; f < _uncoveredTuples[d].Length; f++ )
 574                     {
 575                         List<FeatureTuple> tuples = _uncoveredTuples[d][f];
 576
 577                         for ( int i = tuples.Count - 1; i >= 0; i-- )
 578                         {
 579                             if ( testCase.IsTupleCovered( tuples[i] ) )
 580                             {
 581                                 tuples.RemoveAt( i );
 582                             }
 583                         }
 584                     }
 585                 }
 586             }
 587
 588 #if DEBUG
 589             private void SelfTest( List<TestCaseInfo> testCases )
 590             {
 591                 for ( int d1 = 0; d1 < _dimensions.Length - 1; d1++ )
 592                 {
 593                     for ( int d2 = d1 + 1; d2 < _dimensions.Length; d2++ )
 594                     {
 595                         for ( int f1 = 0; f1 < _dimensions[d1]; f1++ )
 596                         {
 597                             for ( int f2 = 0; f2 < _dimensions[d2]; f2++ )
 598                             {
 599                                 FeatureTuple tuple = new FeatureTuple( new FeatureInfo( d1, f1 ), new FeatureInfo( d2, f2 ) );
 600
 601                                 if ( !IsTupleCovered( testCases, tuple ) )
 602                                 {
 603                                     throw new InvalidOperationException( string.Format( "PairwiseStrategy : Not all pairs are covered : {0}", tuple.ToString() ) );
 604                                 }
 605                             }
 606                         }
 607                     }
 608                 }
 609             }
 610
 611             private bool IsTupleCovered( List<TestCaseInfo> testCases, FeatureTuple tuple )
 612             {
 613                 foreach ( TestCaseInfo testCase in testCases )
 614                 {
 615                     if ( testCase.IsTupleCovered( tuple ) )
 616                     {
 617                         return true;
 618                     }
 619                 }
 620
 621                 return false;
 622             }
 623 #endif
 624         }
 625
 626         #endregion
 627
 628         /// <summary>
 629         /// Gets the test cases generated by this strategy instance.
 630         /// </summary>
 631         /// <returns>A set of test cases.</returns>
 632         public IEnumerable<ITestCaseData> GetTestCases(IEnumerable[] sources)
 633         {
 634             List<ITestCaseData> testCases = new List<ITestCaseData>();
 635             List<object>[] valueSet = CreateValueSet(sources);
 636             int[] dimensions = CreateDimensions(valueSet);
 637
 638             IEnumerable pairwiseTestCases = new PairwiseTestCaseGenerator().GetTestCases( dimensions );
 639
 640             foreach (TestCaseInfo pairwiseTestCase in pairwiseTestCases)
 641             {
 642                 object[] testData = new object[pairwiseTestCase.Features.Length];
 643
 644                 for (int i = 0; i < pairwiseTestCase.Features.Length; i++)
 645                 {
 646                     testData[i] = valueSet[i][pairwiseTestCase.Features[i]];
 647                 }
 648
 649                 TestCaseParameters parms = new TestCaseParameters(testData);
 650                 testCases.Add(parms);
 651             }
 652
 653             return testCases;
 654         }
 655
 656         private List<object>[] CreateValueSet(IEnumerable[] sources)
 657         {
 658             var valueSet = new List<object>[sources.Length];
 659
 660             for (int i = 0; i < valueSet.Length; i++)
 661             {
 662                 var values = new List<object>();
 663
 664                 foreach (object value in sources[i])
 665                 {
 666                     values.Add(value);
 667                 }
 668
 669                 valueSet[i] = values;
 670             }
 671
 672             return valueSet;
 673         }
 674
 675         private int[] CreateDimensions(List<object>[] valueSet)
 676         {
 677             int[] dimensions = new int[valueSet.Length];
 678
 679             for (int i = 0; i < valueSet.Length; i++)
 680             {
 681                 dimensions[i] = valueSet[i].Count;
 682             }
 683
 684             return dimensions;
 685         }
 686     }
 687 }