「実践プロパティベーステスト」を読んで
tokadev です。
「実践プロパティベーステスト」を最近読んだので、備忘録がてら書き残しておきます。
本書のサンプルコードは Erlang で記述されていますが、勉強と理解のために TypeScript fast-check を使用して書いています。
第1章:プロパティベーステストの基礎
プロパティベーステスト(Property-Based Testing: PBT)は、少ないコードで強力なテストを実現する手法。従来の例示ベースのテストとは違い、プログラムの振る舞いに関する抽象的なルールを定義しフレームワークが自動的にテストケースを生成する。
import * as fc from "fast-check";
test("addition is commutative", () => {
fc.assert(
fc.property(fc.integer(), fc.integer(), (a, b) => {
return a + b === b + a;
})
);
});
キャッシュレジスターの例
従来のテスト:
interface Money {
denomination: number;
count: number;
}
type Register = Money[];
type Change = Money[];
const register: Register = [
{ denomination: 20.0, count: 1 },
{ denomination: 10.0, count: 2 },
{ denomination: 5.0, count: 4 },
{ denomination: 1.0, count: 10 },
{ denomination: 0.25, count: 10 },
{ denomination: 0.01, count: 100 },
];
expect(calculateChange(register, 10.0, 20.0)).toEqual([
{ denomination: 10.0, count: 1 },
]);
expect(calculateChange(register, 9.75, 20.0)).toEqual([
{ denomination: 10.0, count: 1 },
{ denomination: 0.25, count: 1 },
]);
プロパティベースアプローチ:
import * as fc from "fast-check";
// プロパティテスト
test("change amount is correct", () => {
const registerGen = fc.array(
fc.record({
denomination: fc.double({ min: 0.01, max: 100 }),
count: fc.integer({ min: 0, max: 100 }),
}),
{ minLength: 1 }
);
fc.assert(
fc.property(
registerGen,
fc.double({ min: 0.01, max: 100 }),
fc.double({ min: 0.01, max: 200 }),
(register, priceToPay, moneyPaid) => {
fc.pre(moneyPaid >= priceToPay);
try {
const change = calculateChange(register, priceToPay, moneyPaid);
const changeSum = sumChange(change);
const expectedChange =
Math.round((moneyPaid - priceToPay) * 100) / 100;
return (
Math.abs(changeSum - expectedChange) < 0.001 &&
isFewestPieces(register, change)
);
} catch (error) {
return error.message === "Cannot make exact change";
}
}
)
);
});
具体的なテストケースやテストデータを列挙するのではなく、プログラムの振る舞いに関する抽象的なルールを定義して、実装者が想定していないバグの発見に繋がる手法であること。
習得するために時間はかかるが、ソフトウェアの品質アップに貢献するツールである。
第2章:プロパティを書く
プロパティの種類
- ステートレスプロパティ: 独立していて状態を持たないコンポーネントのテスト
- ステートフルプロパティ: 複雑で状態を持つシステムテスト
収縮(Shrinking)機能
- テストが失敗した場合、PropErは最小の失敗ケースを見つけようとする
- これにより、デバッグが容易になる
- 例:
[-1]
は[-38,-1]
よりもデバッグしやすい
Property failed after 6 tests
{ seed: 1234567890, path: "0:0:0", endOnFailure: true }
Counterexample: [[-3, -1]]
Shrunk 2 time(s)
Got error: Error: ...
Last minimal counterexample: [[-1]]
第 3 章:プロパティで考える
1. モデル化(Modeling)
- 単純な参照実装を使ってテスト対象のコードを検証
- 既存のライブラリ関数や簡単な実装と比較
- 例:lists:max/1を使ってbiggest/1をテスト
function sort<T>(arr: T[]): T[] {
return [...arr].sort((a, b) => {
if (a < b) return -1;
if (a > b) return 1;
return 0;
});
}
test("sort matches built-in sort", () => {
fc.assert(
fc.property(fc.array(fc.integer()), (arr) => {
const result = sort(arr);
const expected = [...arr].sort((a, b) => a - b);
return JSON.stringify(result) === JSON.stringify(expected);
})
);
});
2. 事例テストの汎化(Generalizing Example Tests)
- 既存のユニットテストからプロパティを導出
- 具体的な入力から一般的なルールを抽出
- 例:last関数の具体的なテストから一般的なプロパティへ
// 従来のユニットテスト
test("last element tests", () => {
expect(last(["a", "b", "c"])).toBe("c");
expect(last([1])).toBe(1);
});
// プロパティテストに変換
function last<T>(arr: T[]): T {
if (arr.length === 0) throw new Error("Empty array");
return arr[arr.length - 1];
}
test("last returns final element", () => {
fc.assert(
fc.property(fc.array(fc.anything(), { minLength: 1 }), (arr) => {
const result = last(arr);
return result === arr[arr.length - 1];
})
);
});
3. 不変条件(Invariants)
- 操作前後で常に真であるべき条件を特定
- 入力や内部状態に関係なく保持される性質
- 例:ソートされたリストの要素数、順序性
function sameElements<T>(arr1: T[], arr2: T[]): boolean {
if (arr1.length !== arr2.length) return false;
const sorted1 = [...arr1].sort();
const sorted2 = [...arr2].sort();
for (let i = 0; i < sorted1.length; i++) {
if (sorted1[i] !== sorted2[i]) return false;
}
return true;
}
test("sort preserves length", () => {
fc.assert(
fc.property(fc.array(fc.integer()), (arr) => {
const sorted = sort(arr);
return sorted.length === arr.length;
})
);
});
test("sort preserves elements", () => {
fc.assert(
fc.property(fc.array(fc.integer()), (arr) => {
const sorted = sort(arr);
return sameElements(arr, sorted);
})
);
});
4. 対称プロパティ(Symmetric Properties)
- エンコード/デコード、圧縮/展開など逆操作のテスト
- A → B → A の形で元に戻ることを確認
- ラウンドトリップテストとも呼ばれる
test("base64 encode/decode roundtrip", () => {
fc.assert(
fc.property(fc.string(), (str) => {
const encoded = Buffer.from(str, "utf8").toString("base64");
const decoded = Buffer.from(encoded, "base64").toString("utf8");
return decoded === str;
})
);
});
test("JSON stringify/parse roundtrip", () => {
fc.assert(
fc.property(
fc.oneof(
fc.string(),
fc.integer(),
fc.double(),
fc.boolean(),
fc.constantFrom(null)
),
(value) => {
const serialized = JSON.stringify(value);
const deserialized = JSON.parse(serialized);
return deserialized === value;
}
)
);
});
※ TypeScript で JSON.stringify/parse を利用したラウンドトリップテストを行う場合、プリミティブ型やシンプルなオブジェクトには有効だが undefined
や NaN
を含む一部のデータ型は元の値と一致しない場合があるので注意が必要。
第 4 章:カスタムジェネレーター
デフォルトジェネレーターでは対応しきれない特殊なテストケースに対して、以下のような高度な技法を適用することで、より効果的なテストを実現できることが示されている。
- 統計情報の収集
- データ変換
- フィルタリング
- 確率制御
- 再帰処理
- シンボリックコール
第 5 章:信頼できるテスト
単体テストをはじめとし、段階的にテストを構築していく過程を通して信頼性の高いソフトウェアを開発するための技法が紹介されている。データの抽象化、エラーハンドリング、エッジケース処理など、実際の開発で遭遇する課題への対処法について触れられており、プロパティベーステストは単なる理論的なツールではなく、実用的な開発手法であることを示している。
誕生日メール送信システムの構築
CSV パーサーのプロパティ
対称プロパティの活用:
interface Employee {
lastName: string;
firstName: string;
dateOfBirth: string;
email: string;
}
class CsvParser {
static encode(employees: Employee[]): string {
const header = "last_name, first_name, date_of_birth, email";
const rows = employees.map(
(emp) =>
`${emp.lastName}, ${emp.firstName}, ${emp.dateOfBirth}, ${emp.email}`
);
return [header, ...rows].join("\n");
}
static decode(csv: string): Employee[] {
const lines = csv.split("\n");
const dataLines = lines.slice(1); // remove header
return dataLines
.filter((line) => line.trim())
.map((line) => {
const [lastName, firstName, dateOfBirth, email] = line
.split(",")
.map((s) => s.trim());
return { lastName, firstName, dateOfBirth, email };
});
}
}
const employeeGen = fc.record({
lastName: fc.string({ minLength: 1 }).filter((s) => !s.includes(",")),
firstName: fc.string({ minLength: 1 }).filter((s) => !s.includes(",")),
dateOfBirth: fc.date().map((d) => d.toISOString().split("T")[0]),
email: fc.emailAddress(),
});
test("CSV roundtrip property", () => {
fc.assert(
fc.property(fc.array(employeeGen), (employees) => {
const encoded = CsvParser.encode(employees);
const decoded = CsvParser.decode(encoded);
return JSON.stringify(employees) === JSON.stringify(decoded);
})
);
});
データ抽象化
TypeScript の型システムを使った実装の隠蔽:
interface EmployeeData {
[key: string]: any;
}
export interface Employee {
readonly name: string;
readonly email: string;
readonly birthDate: Date;
}
export class EmployeeService {
private employees: EmployeeData[] = [];
constructor(rawData: EmployeeData[]) {
this.employees = rawData;
}
getByEmail(email: string): Employee | null {
const data = this.employees.find((emp) => emp.email === email);
if (!data) return null;
return {
name: `${data.firstName} ${data.lastName}`,
email: data.email,
birthDate: new Date(data.dateOfBirth),
};
}
}
test("employee service properties", () => {
const employeeDataGen = fc.record({
firstName: fc.string({ minLength: 1 }),
lastName: fc.string({ minLength: 1 }),
email: fc.emailAddress(),
dateOfBirth: fc.date().map((d) => d.toISOString()),
});
fc.assert(
fc.property(fc.array(employeeDataGen), (employeeData) => {
const service = new EmployeeService(employeeData);
return employeeData.every((data) => {
const found = service.getByEmail(data.email);
return found !== null && found.email === data.email;
});
})
);
});
第 6 章:プロパティ駆動開発
プロパティを通じてシステムの動作を定義し段階的に機能を実装していくプロセスは、従来のテスト駆動開発を発展させたもの。複雑なジェネレーターの設計とポジティブテスト・ネガティブテストの両方を活用することで、従来の手法では発見が困難な潜在的なバグを系統的に見つけ出すことができることが実証されている。
プロパティ駆動開発の哲学
プロパティ駆動開発(Property-Driven Development)は、従来のテスト駆動開発(TDD)の発展形である。TDDが具体的なテストケースから実装を導き出すのに対し、PDDは抽象的なプロパティから実装を導き出し、より網羅的で堅牢なソフトウェア開発が可能になる。
基本原則
- プロパティファースト: 実装前に満たすべきプロパティを定義
- 反復的洗練: プロパティテストの失敗から実装を改善
- ドメイン知識の形式化: ビジネスルールをプロパティとして表現
- 早期の設計検証: 実装前に設計の妥当性を確認
スーパーマーケット価格計算システムの事例
この章では、実践的な例として、スーパーマーケットの価格計算システムを開発します。このシステムは以下の要件を満たす必要があります:
- 基本価格計算: 商品と価格リストに基づく合計金額の計算
- 特価対応: 「3個で500円」のようなまとめ買い特価への対応
- 価格整合性: 計算結果の正確性と一貫性の保証
- エラーハンドリング: 不正な入力への適切な対応
開発プロセス
1. ドメインモデルの定義
最初に、システムで扱うデータ型を定義します:
-
Item
: 商品名を表す文字列 -
Price
: 価格を表す数値 -
PriceList
: 商品と価格のペアの配列 -
Special
: 特価情報(商品名、必要数量、特価)
2. プロパティの識別
実装前に満たすべきプロパティを列挙します:
基本プロパティ:
- 空の商品リストの合計は0円
- 単一商品の合計は単価と同じ
- 商品の順序を変えても合計は変わらない
- 分割しても合計は変わらない(例:[A,B,C] = [A] + [B,C])
特価プロパティ:
- 特価適用は常に顧客に有利(通常価格以下)
- 特価の部分適用が正しく計算される
- 特価対象外の商品は通常価格で計算される
エラーハンドリングプロパティ:
- 存在しない商品はエラーを発生させる
- 無効な価格リスト(重複商品など)はエラー
- 無効な特価設定(0個で特価など)はエラー
3. 段階的実装
// 基本的な型定義のみ表示
export type Item = string;
export type Price = number;
export type PriceList = Array<[Item, Price]>;
export type Special = [Item, number, Price];
実装の段階的洗練
プロパティ駆動開発では、失敗するテストから始めて、段階的に実装を洗練させていきます:
- 最小実装: 最も単純なケースを通すだけの実装
- プロパティ追加: より複雑なプロパティを追加
- 実装改善: 新しいプロパティを満たすように実装を拡張
- リファクタリング: コードの可読性と保守性を向上
export type Item = string;
export type Price = number;
export type PriceList = Array<[Item, Price]>;
export type Special = [Item, number, Price]; // [ItemName, Count, SpecialPrice]
export type SpecialList = Special[];
export class Checkout {
static total(itemList: Item[], priceList: PriceList, specials: SpecialList): Price {
if (!this.validPriceList(priceList)) {
throw new Error('invalid_price_list');
}
if (!this.validSpecialList(specials)) {
throw new Error('invalid_special_list');
}
const counts = this.countSeen(itemList);
const [countsLeft, specialPrice] = this.applySpecials(counts, specials);
const regularPrice = this.applyRegular(countsLeft, priceList);
return specialPrice + regularPrice;
}
private static countSeen(itemList: Item[]): Array<[Item, number]> {
const countMap: { [key: string]: number } = {};
itemList.forEach(item => {
countMap[item] = (countMap[item] || 0) + 1;
});
return Object.entries(countMap);
}
private static applySpecials(
items: Array<[Item, number]>,
specials: SpecialList
): [Array<[Item, number]>, Price] {
let totalSpecialPrice = 0;
const countsLeft = items.map(([name, count]) => {
const special = specials.find(([specialName]) => specialName === name);
if (!special) {
return [name, count] as [Item, number];
}
const [, needed, value] = special;
const timesApplied = Math.floor(count / needed);
const remaining = count % needed;
totalSpecialPrice += timesApplied * value;
return [name, remaining] as [Item, number];
});
return [countsLeft, totalSpecialPrice];
}
private static applyRegular(items: Array<[Item, number]>, priceList: PriceList): Price {
let totalPrice = 0;
items.forEach(([name, count]) => {
const priceEntry = priceList.find(([itemName]) => itemName === name);
if (!priceEntry) {
throw new Error(`unknown_item: ${name}`);
}
const [, price] = priceEntry;
totalPrice += count * price;
});
return totalPrice;
}
static validPriceList(priceList: PriceList): boolean {
if (priceList.length === 0) return true;
const names = priceList.map(([name]) => name);
const uniqueNames = [...new Set(names)];
return names.length === uniqueNames.length;
}
static validSpecialList(specialList: SpecialList): boolean {
if (specialList.length === 0) return true;
if (specialList.some(([, count]) => count === 0)) {
return false;
}
const names = specialList.map(([name]) => name);
const uniqueNames = [...new Set(names)];
return names.length === uniqueNames.length;
}
}
基本的なプロパティテスト(特価なし)
最初は特価なしの単純なケースから始め、以下のプロパティを検証する。
- 商品リストの合計金額が手動計算と一致する
- 空のリストの合計は0円
- 商品の順序を変えても合計は同じ
- 部分リストの合計を足し合わせると全体の合計と同じ
test('checkout total without specials', () => {
const itemGen = fc.string({minLength: 1, maxLength: 10});
const priceListGen = fc.array(fc.tuple(itemGen, fc.double({min: 0.01, max: 100})));
const itemListGen = fc.array(itemGen);
fc.assert(fc.property(
itemListGen,
priceListGen,
(items, priceList) => {
fc.pre(Checkout.validPriceList(priceList));
const priceMap = new Map(priceList);
fc.pre(items.every(item => priceMap.has(item)));
const total = Checkout.total(items, priceList, []);
const expectedTotal = items.reduce((sum, item) => {
const price = priceMap.get(item) || 0;
return sum + price;
}, 0);
return Math.abs(total - expectedTotal) < 0.001;
}
));
});
特価を含む複雑なプロパティ
特価を含むテストでは、以下の点を検証する。
通常価格より安い特価を生成し、実際のビジネスルールを反映させる。テスト実行時は、手動計算結果と自動計算結果を比較して正確性を検証する。
- 特価計算の正確性: まとめ買い特価が正しく適用される
- 部分適用: 特価に満たない分は通常価格で計算される
- 複数特価の組み合わせ: 異なる商品の特価が独立して適用される
- エラー処理: 無効な入力に対して適切なエラーが発生する
test('checkout total with specials', () => {
const itemGen = fc.string({minLength: 1, maxLength: 5});
const priceGen = fc.double({min: 0.01, max: 10});
const specialGen = fc.tuple(itemGen, fc.integer({min: 2, max: 5}), priceGen)
.filter(([, count, specialPrice]) => count > 1 && specialPrice > 0) as fc.Arbitrary<Special>;
const setupGen = fc.record({
items: fc.array(itemGen, {maxLength: 20}),
priceList: fc.array(fc.tuple(itemGen, priceGen)),
specials: fc.array(specialGen)
});
fc.assert(fc.property(
setupGen,
({items, priceList, specials}) => {
fc.pre(Checkout.validPriceList(priceList));
fc.pre(Checkout.validSpecialList(specials));
const priceMap = new Map(priceList);
fc.pre(items.every(item => priceMap.has(item)));
try {
const total = Checkout.total(items, priceList, specials);
const itemCounts = new Map<string, number>();
items.forEach(item => {
itemCounts.set(item, (itemCounts.get(item) || 0) + 1);
});
let expectedTotal = 0;
itemCounts.forEach((count, item) => {
const special = specials.find(([specialItem]) => specialItem === item);
const regularPrice = priceMap.get(item) || 0;
if (special) {
const [, specialCount, specialPrice] = special;
const specialApplications = Math.floor(count / specialCount);
const remainingItems = count % specialCount;
expectedTotal += specialApplications * specialPrice + remainingItems * regularPrice;
} else {
expectedTotal += count * regularPrice;
}
});
return Math.abs(total - expectedTotal) < 0.001;
} catch (error) {
return error.message.includes('unknown_item') ||
error.message.includes('invalid');
}
}
));
});
ネガティブテスト
ネガティブテストでは、以下の無効な入力パターンを検証し、適切なエラーメッセージが返されることを確認する。
- 重複商品: 価格リスト内に同一商品が複数存在
- 無効な特価設定: 0個で特価など、ビジネスロジックに反する設定
- 存在しない商品: 価格リストに存在しない商品の購入試行
- 負の価格: 現実的でない価格設定
test('checkout handles invalid inputs appropriately', () => {
const itemGen = fc.string();
const priceGen = fc.oneof(fc.double(), fc.integer(), fc.constant(-1));
const invalidSetupGen = fc.oneof(
fc.record({
items: fc.array(itemGen),
priceList: fc.array(fc.tuple(fc.constant('duplicate'), priceGen), {minLength: 2}),
specials: fc.array(fc.tuple(itemGen, fc.integer({min: 1, max: 5}), priceGen))
}),
fc.record({
items: fc.array(itemGen),
priceList: fc.array(fc.tuple(itemGen, priceGen)),
specials: fc.array(fc.tuple(itemGen, fc.constant(0), priceGen), {minLength: 1})
}),
fc.record({
items: fc.array(fc.constant('nonexistent')),
priceList: fc.array(fc.tuple(fc.string().filter(s => s !== 'nonexistent'), priceGen)),
specials: fc.array(fc.tuple(itemGen, fc.integer({min: 1, max: 5}), priceGen))
})
);
fc.assert(fc.property(
invalidSetupGen,
({items, priceList, specials}) => {
try {
Checkout.total(items, priceList as PriceList, specials as SpecialList);
return false
} catch (error) {
const message = error.message;
return message.includes('unknown_item') ||
message.includes('invalid_special_list') ||
message.includes('invalid_price_list');
}
}
));
});
順序無依存性のプロパティ
商品リストの順序を変えても合計金額が変わらないことを検証する。
これは重要な不変条件であり、実装の健全性を示す指標となる。
test('checkout total is independent of item order', () => {
const setupGen = fc.record({
items: fc.array(fc.string({minLength: 1}), {maxLength: 10}),
priceList: fc.array(fc.tuple(fc.string({minLength: 1}), fc.double({min: 0.01, max: 100}))),
specials: fc.array(fc.tuple(fc.string({minLength: 1}), fc.integer({min: 2, max: 5}), fc.double({min: 0.01, max: 50})))
});
fc.assert(fc.property(
setupGen,
({items, priceList, specials}) => {
fc.pre(Checkout.validPriceList(priceList));
fc.pre(Checkout.validSpecialList(specials));
const priceMap = new Map(priceList);
fc.pre(items.every(item => priceMap.has(item)));
try {
const total1 = Checkout.total(items, priceList, specials);
const shuffledItems = [...items].sort(() => Math.random() - 0.5);
const total2 = Checkout.total(shuffledItems, priceList, specials);
return Math.abs(total1 - total2) < 0.001;
} catch (error) {
try {
const shuffledItems = [...items].sort(() => Math.random() - 0.5);
Checkout.total(shuffledItems, priceList, specials);
return false; // 片方だけエラーになった場合は失敗
} catch (error2) {
return error.message === error2.message; // 同じエラーメッセージ
}
}
}
));
});
第 7 章:収縮(Shrinking)
収縮の基本原理
- 目的: 失敗した複雑なテストケースを最も単純な形に変換
- デフォルト収縮の傾向:
- 数値: 大きな数 → 小さな数 → 0
- 文字列: 長い文字列 → 短い文字列 → 空文字列
- 配列: 多要素 → 少要素 → 空配列
年ジェネレーターの収縮戦略
現実的な範囲(1970-2030)に収縮点を設定することで、デバッグ時により理解しやすい反例を得られる。範囲外の値は自動的に調整され、テスト失敗時には現実的な年が反例として提示される。
const yearGen = fc.integer({min: 0, max: 9999})
.map(year => {
// デフォルトの収縮点を現実的な年に設定
if (year >= 1970 && year <= 2030) {
return year; // 現実的な年はそのまま
} else if (year >= 1900 && year <= 2100) {
return year; // 広めの範囲もそのまま
}
return Math.max(1970, Math.min(2030, year)); // 範囲外は調整
});
test('year validation with custom shrinking', () => {
fc.assert(fc.property(
yearGen,
(year) => {
return year >= 1900 && year <= 2100; // 意図的にたまに失敗させる
}
));
});
タイムゾーンの収縮
タイムゾーンジェネレーターでは、一般的な時差(0, 15, 30, 45分)に収縮することで実際のタイムゾーンに近い反例を生成しエッジケースの特定が容易になる。
interface Timezone {
sign: '+' | '-';
hours: number;
minutes: number;
}
const timezoneGen = fc.record({
sign: fc.constantFrom('+', '-') as fc.Arbitrary<'+' | '-'>,
hours: fc.integer({min: 0, max: 23}).map(h => {
// より現実的な時間に収縮
if (h <= 14) return h;
return h % 15; // 0, 15, 30, 45などに寄せる
}),
minutes: fc.constantFrom(0, 15, 30, 45)
});
function formatTimezone(tz: Timezone): string {
return `${tz.sign}${tz.hours.toString().padStart(2, '0')}:${tz.minutes.toString().padStart(2, '0')}`;
}
test('timezone formatting', () => {
fc.assert(fc.property(
timezoneGen,
(tz) => {
const formatted = formatTimezone(tz);
const regex = /^[+-]\d{2}:\d{2}$/;
return regex.test(formatted);
}
));
});
効率的な収縮のためのカスタムジェネレーター
二分木の収縮戦略
- 重み付けによる制御: リーフノードに高い重みを設定し、収縮時に優先的にシンプルな構造へ変換
- 深さ制限: 最大深度を設定し、無限再帰を防止
- 段階的簡略化: 内部ノードからリーフノードへの変換を優先
この戦略により、複雑な木構造でのバグも、最小限のノード数で再現可能な反例まで収縮される。
interface TreeNode {
value: number;
left?: TreeNode;
right?: TreeNode;
}
const treeGen = (maxDepth: number): fc.Arbitrary<TreeNode> => {
if (maxDepth <= 0) {
return fc.record({
value: fc.integer()
});
}
return fc.oneof(
// リーフノード
{arbitrary: fc.record({ value: fc.integer() }), weight: 3},
// 内部ノード(収縮時に優先的にリーフに変換される)
{arbitrary: fc.record({
value: fc.integer(),
left: treeGen(maxDepth - 1),
right: treeGen(maxDepth - 1)
}), weight: 1}
);
};
function treeHeight(tree: TreeNode): number {
if (!tree.left && !tree.right) return 1;
const leftHeight = tree.left ? treeHeight(tree.left) : 0;
const rightHeight = tree.right ? treeHeight(tree.right) : 0;
return 1 + Math.max(leftHeight, rightHeight);
}
test('tree height calculation', () => {
fc.assert(fc.property(
treeGen(5),
(tree) => {
const height = treeHeight(tree);
return height >= 1; // 最低でも高さ1
}
));
});
パス最適化による収縮
- 最短経路への収縮: バグを再現する最短パスを発見
- デバッグの効率化: 冗長な移動を除去し、問題の本質に集中
- 理解しやすい反例: 人間が理解しやすい形式での表示
type PathStep = 'N' | 'S' | 'E' | 'W';
const pathGen = fc.array(
fc.constantFrom('N', 'S', 'E', 'W') as fc.Arbitrary<PathStep>,
{maxLength: 50}
).map(steps => {
// 収縮時に無意味な往復を除去
const optimized: PathStep[] = [];
for (const step of steps) {
const last = optimized[optimized.length - 1];
// 直前のステップと逆方向なら両方削除(往復を除去)
if (last &&
((last === 'N' && step === 'S') ||
(last === 'S' && step === 'N') ||
(last === 'E' && step === 'W') ||
(last === 'W' && step === 'E'))) {
optimized.pop();
} else {
optimized.push(step);
}
}
return optimized;
});
function calculatePosition(path: PathStep[]): {x: number, y: number} {
let x = 0, y = 0;
for (const step of path) {
switch (step) {
case 'N': y++; break;
case 'S': y--; break;
case 'E': x++; break;
case 'W': x--; break;
}
}
return {x, y};
}
test('path optimization maintains final position', () => {
fc.assert(fc.property(
pathGen,
(optimizedPath) => {
const pos = calculatePosition(optimizedPath);
// 最適化されたパスに無意味な往復がないことを確認
for (let i = 1; i < optimizedPath.length; i++) {
const current = optimizedPath[i];
const previous = optimizedPath[i-1];
const isOpposite =
(current === 'N' && previous === 'S') ||
(current === 'S' && previous === 'N') ||
(current === 'E' && previous === 'W') ||
(current === 'W' && previous === 'E');
if (isOpposite) {
return false; // 往復が見つかったら失敗
}
}
return true;
}
));
});
第 8 章:標的型プロパティ
基本概念
標的型プロパティは、テストデータの生成を動的に最適化しより興味深いテストケースを発見する技術である。
- フィードバックループ: 各テスト実行の結果が次のテストデータ生成に影響
- メトリクス最適化: 特定の指標を最大化または最小化
- 探索的テスト: 通常のランダムテストでは見つかりにくいエッジケースの発見
- 統計的分析: テスト結果の収集と分析による洞察
fast-check
fast-check では、完全な標的型プロパティはサポートされていないが、以下のアプローチで同様の効果を得られる。
- 統計情報の収集: テスト実行中にメトリクスを記録
- 事後分析: 収集したデータをソートして最適なケースを特定
- カスタムジェネレーター: 特定の傾向を持つデータ生成
経路探索の例
基本的な標的型アプローチ
interface Position {
x: number;
y: number;
}
type Direction = 'up' | 'down' | 'left' | 'right';
function followPath(directions: Direction[]): Position {
return directions.reduce((pos, dir) => {
switch (dir) {
case 'up': return {x: pos.x, y: pos.y + 1};
case 'down': return {x: pos.x, y: pos.y - 1};
case 'left': return {x: pos.x - 1, y: pos.y};
case 'right': return {x: pos.x + 1, y: pos.y};
}
}, {x: 0, y: 0});
}
test('path exploration with statistics', () => {
const pathGen = fc.array(
fc.constantFrom('up', 'down', 'left', 'right') as fc.Arbitrary<Direction>,
{maxLength: 20}
);
const results: Array<{path: Direction[], distance: number}> = [];
fc.assert(fc.property(
pathGen,
(path) => {
const endPos = followPath(path);
const distance = endPos.x - endPos.y;
results.push({path, distance});
return true;
}
), {numRuns: 1000});
results.sort((a, b) => b.distance - a.distance);
const topResults = results.slice(0, 10);
console.log('Top 10 paths for maximizing (x - y):');
topResults.forEach((result, index) => {
const endPos = followPath(result.path);
console.log(`${index + 1}: distance=${result.distance}, end=(${endPos.x},${endPos.y}), path length=${result.path.length}`);
});
});
複雑な最適化メトリクス
複数のメトリクスを同時に追跡することで、より洗練された分析が可能になる。
- 最終到達距離: 終点が原点から最も遠いパス
- 探索範囲: 最も多くのユニークな位置を訪問したパス
- 効率性: 最短歩数で目的地に到達したパス
- 複雑度: 最も複雑な動きをしたパス
interface PathMetrics {
finalDistance: number;
pathLength: number;
uniquePositionsVisited: number;
maxDistanceFromOrigin: number;
}
function analyzePath(path: Direction[]): PathMetrics {
const positions: Position[] = [{x: 0, y: 0}];
const visited = new Set(['0,0']);
let maxDistance = 0;
path.reduce((currentPos, direction) => {
const newPos = followPath([direction]);
const nextPos = {
x: currentPos.x + newPos.x,
y: currentPos.y + newPos.y
};
positions.push(nextPos);
visited.add(`${nextPos.x},${nextPos.y}`);
const distanceFromOrigin = Math.sqrt(nextPos.x * nextPos.x + nextPos.y * nextPos.y);
maxDistance = Math.max(maxDistance, distanceFromOrigin);
return nextPos;
}, {x: 0, y: 0});
const finalPos = positions[positions.length - 1];
return {
finalDistance: finalPos.x - finalPos.y,
pathLength: path.length,
uniquePositionsVisited: visited.size,
maxDistanceFromOrigin: maxDistance
};
}
test('complex path optimization', () => {
const pathGen = fc.array(
fc.constantFrom('up', 'down', 'left', 'right') as fc.Arbitrary<Direction>,
{minLength: 5, maxLength: 30}
);
const results: Array<{path: Direction[], metrics: PathMetrics}> = [];
fc.assert(fc.property(
pathGen,
(path) => {
const metrics = analyzePath(path);
results.push({path, metrics});
return true;
}
), {numRuns: 2000});
const furthestPaths = results
.sort((a, b) => Math.abs(b.metrics.finalDistance) - Math.abs(a.metrics.finalDistance))
.slice(0, 5);
furthestPaths.forEach((result, i) => {
const endPos = followPath(result.path);
console.log(`${i+1}: (${endPos.x},${endPos.y}), distance=${result.metrics.finalDistance}`);
});
const mostExplorative = results
.sort((a, b) => b.metrics.uniquePositionsVisited - a.metrics.uniquePositionsVisited)
.slice(0, 3);
mostExplorative.forEach((result, i) => {
console.log(`${i+1}: visited ${result.metrics.uniquePositionsVisited} unique positions in ${result.metrics.pathLength} steps`);
});
});
アルゴリズムの性能測定
クイックソートの性能測定
標的型プロパティをアルゴリズムの性能分析に応用することで、最悪ケースの発見や性能特性の理解を深めることに役立つ。
- 入力パターン別の性能: ランダム、ソート済み、逆順、重複多数
- サイズと実行時間の関係: O(n log n)の検証
- 最悪ケースの特定: ピボット選択が悪いケース
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) return [...arr];
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}
function measureSortingTime(arr: number[]): number {
const start = performance.now();
quickSort(arr);
const end = performance.now();
return end - start;
}
test('quicksort performance characteristics', () => {
const performanceResults: Array<{
arraySize: number;
sortTime: number;
arrayType: 'random' | 'sorted' | 'reverse' | 'duplicates'
}> = [];
fc.assert(fc.property(
fc.array(fc.integer({min: -1000, max: 1000}), {maxLength: 1000}),
(arr) => {
if (arr.length < 10) return true;
const sortTime = measureSortingTime(arr);
performanceResults.push({
arraySize: arr.length,
sortTime,
arrayType: 'random'
});
return sortTime < 100;
}
), {numRuns: 100});
fc.assert(fc.property(
fc.integer({min: 10, max: 1000}),
(size) => {
const sortedArr = Array.from({length: size}, (_, i) => i);
const sortTime = measureSortingTime(sortedArr);
performanceResults.push({
arraySize: size,
sortTime,
arrayType: 'sorted'
});
return sortTime < 50;
}
), {numRuns: 50});
fc.assert(fc.property(
fc.integer({min: 10, max: 1000}),
(size) => {
const reverseArr = Array.from({length: size}, (_, i) => size - i);
const sortTime = measureSortingTime(reverseArr);
performanceResults.push({
arraySize: size,
sortTime,
arrayType: 'reverse'
});
return sortTime < 200;
}
), {numRuns: 50});
['random', 'sorted', 'reverse', 'duplicates'].forEach(type => {
const typeResults = performanceResults.filter(r => r.arrayType === type);
if (typeResults.length === 0) return;
const avgTime = typeResults.reduce((sum, r) => sum + r.sortTime, 0) / typeResults.length;
const maxTime = Math.max(...typeResults.map(r => r.sortTime));
const avgSize = typeResults.reduce((sum, r) => sum + r.arraySize, 0) / typeResults.length;
});
});
カスタム最適化関数
文字列検索の最悪ケース探索
素朴な文字列検索アルゴリズムの性能を分析し、標的型プロパティにより以下のパターンを発見できる。
これらの発見は、より効率的なアルゴリズムの必要性を示す。(KMP, Boyer-Moore, ...)
- 部分一致が多いパターン: "aaa"を"aaab"から検索するようなケース
- 繰り返しパターン: 同じ文字の連続
- 近似パターン: 最後の文字だけが異なるパターン
カスタム最適化関数
文字列検索の最適化
function naiveStringSearch(text: string, pattern: string): number[] {
const matches: number[] = [];
for (let i = 0; i <= text.length - pattern.length; i++) {
let match = true;
for (let j = 0; j < pattern.length; j++) {
if (text[i + j] !== pattern[j]) {
match = false;
break;
}
}
if (match) {
matches.push(i);
}
}
return matches;
}
test('string search worst-case optimization', () => {
const worstCases: Array<{text: string, pattern: string, comparisons: number}> = [];
const searchCaseGen = fc.tuple(
fc.string({minLength: 10, maxLength: 100}),
fc.string({minLength: 2, maxLength: 10})
).filter(([text, pattern]) => pattern.length <= text.length);
fc.assert(fc.property(
searchCaseGen,
([text, pattern]) => {
let comparisons = 0;
for (let i = 0; i <= text.length - pattern.length; i++) {
for (let j = 0; j < pattern.length; j++) {
comparisons++;
if (text[i + j] !== pattern[j]) {
break;
}
}
}
worstCases.push({text, pattern, comparisons});
const maxComparisons = (text.length - pattern.length + 1) * pattern.length;
return comparisons <= maxComparisons;
}
), {numRuns: 1000});
worstCases.sort((a, b) => b.comparisons - a.comparisons);
console.log('\n=== Worst-case String Search Patterns ===');
worstCases.slice(0, 5).forEach((result, i) => {
console.log(`${i+1}: "${result.pattern}" in "${result.text.substring(0, 20)}..." (${result.comparisons} comparisons)`);
});
const worstPattern = worstCases[0];
console.log(`\nWorst case analysis:`);
console.log(`Pattern: "${worstPattern.pattern}"`);
console.log(`Text length: ${worstPattern.text.length}`);
console.log(`Comparisons: ${worstPattern.comparisons}`);
console.log(`Efficiency: ${(worstPattern.comparisons / (worstPattern.text.length * worstPattern.pattern.length) * 100).toFixed(1)}% of theoretical max`);
});
第 9 章:ステートフルプロパティ
大きくて複雑な状態を持つシステムのバグを比較的小さなテストで発見するステートフルプロパティテストについて詳しく解説されており、これは「コードが何をすべきか」は単純でも「それをコードでどう実現するか」が複雑な場合に有効な手法である。
ステートフルプロパティテスト
- 形式手法とまではいかないモデル検査の亜種
- システムの予測可能なモデルを定義し、一連のコマンドを生成してモデルと実際のシステムの結果を比較
- 両者が合致すればテスト成功、合致しなければ失敗
ステートフルプロパティの要素
- モデル: システムを高水準から見たときに何をすべきかを表現
- コマンドのジェネレーター: プログラムの実行手順を表現
- 実際のシステム: モデルと照らし合わせて検証する対象
モデルの構成要素
- システムの状態を表現するデータ構造: システムが保持・取得可能であると期待されるデータ
- 状態変換関数(next_state): システムに適用可能なコマンドに応じてモデルの状態を変換
コマンドの構成要素
- シンボリックコール: モデルに適用しうるコールのリストと引数ジェネレーター
- 前提条件: 各シンボリックコールを適用する意味があるかをモデルの現在の状態に応じて決定する関数
ステートフルテストのプロセス
- 初期状態の定義: モデルと実装を同じ状態から開始
- コマンドの実行: 同じコマンドを両方に適用
- 結果の比較: モデルと実装の結果が一致するか検証
- 状態の一貫性確認: 内部状態の整合性をチェック
ステートフルテストの利点
- 複雑なシナリオの検証: 長い操作シーケンスを自動生成
- エッジケースの発見: 予想外の操作順序をテスト
- 並行性の検証: 同時操作の一貫性を確認
- リグレッションの防止: リファクタリング時のセーフティネット
LRUキャッシュシステムの実例
LRUキャッシュの実装例
LRU キャッシュは、ステートフルテストに有効である。
- 複数の状態要素: エントリー、アクセス順序、サイズ制限
- 複雑な振る舞い: 削除ロジック、更新、検索の組み合わせ
- エッジケース: 容量制限時の振る舞い、空き状態での操作
TypeScript実装
export interface CacheEntry {
key: string;
value: any;
order: number;
}
export interface CacheState {
entries: Map<string, CacheEntry>;
maxSize: number;
currentOrder: number;
count: number;
}
export type CacheResult<T> =
| { success: true; value: T }
| { success: false; error: string };
export class Cache {
private state: CacheState;
constructor(maxSize: number = 10) {
this.state = {
entries: new Map(),
maxSize,
currentOrder: 0,
count: 0
};
}
find(key: string): CacheResult<any> {
const entry = this.state.entries.get(key);
if (entry) {
return { success: true, value: entry.value };
} else {
return { success: false, error: 'not_found' };
}
}
cache(key: string, value: any): CacheResult<void> {
try {
const existingEntry = this.state.entries.get(key);
if (existingEntry) {
existingEntry.value = value;
this.state.entries.set(key, existingEntry);
} else {
if (this.state.count >= this.state.maxSize) {
this.removeOldestEntry();
}
const newEntry: CacheEntry = {
key,
value,
order: this.state.currentOrder++
};
this.state.entries.set(key, newEntry);
this.state.count = this.state.entries.size;
}
return { success: true, value: undefined };
} catch (error) {
return { success: false, error: String(error) };
}
}
flush(): CacheResult<void> {
try {
this.state.entries.clear();
this.state.count = 0;
this.state.currentOrder = 0;
return { success: true, value: undefined };
} catch (error) {
return { success: false, error: String(error) };
}
}
size(): number {
return this.state.count;
}
private removeOldestEntry(): void {
let oldestKey: string | null = null;
let oldestOrder = Infinity;
for (const [key, entry] of this.state.entries) {
if (entry.order < oldestOrder) {
oldestOrder = entry.order;
oldestKey = key;
}
}
if (oldestKey !== null) {
this.state.entries.delete(oldestKey);
this.state.count = this.state.entries.size;
}
}
}
モデルベーステストフレームワーク
LRUキャッシュのモデルベーステストでは、以下のコンポーネントを実装する。
- モデル実装: Mapとアクセス順序配列でシンプルにLRUを表現
- 実装側: 実際のキャッシュクラス、最適化されたデータ構造を使用
- コマンドジェネレーター: cache, find, flushの操作をランダムに生成
- 比較関数: モデルと実装の結果を比較
interface CacheModel {
entries: Map<string, any>;
accessOrder: string[];
maxSize: number;
}
type CacheCommand =
| { type: 'cache', key: string, value: any }
| { type: 'find', key: string }
| { type: 'flush' };
class CacheModelTester {
private model: CacheModel;
private actualCache: Cache;
constructor(maxSize: number) {
this.model = {
entries: new Map(),
accessOrder: [],
maxSize
};
this.actualCache = new Cache(maxSize);
}
executeModelCommand(cmd: CacheCommand): any {
switch (cmd.type) {
case 'cache':
return this.modelCache(cmd.key, cmd.value);
case 'find':
return this.modelFind(cmd.key);
case 'flush':
return this.modelFlush();
}
}
executeActualCommand(cmd: CacheCommand): any {
switch (cmd.type) {
case 'cache':
return this.actualCache.cache(cmd.key, cmd.value);
case 'find':
return this.actualCache.find(cmd.key);
case 'flush':
return this.actualCache.flush();
}
}
private modelCache(key: string, value: any): CacheResult<void> {
if (this.model.entries.has(key)) {
this.model.entries.set(key, value);
this.model.accessOrder = this.model.accessOrder.filter(k => k !== key);
this.model.accessOrder.push(key);
} else {
if (this.model.entries.size >= this.model.maxSize) {
const oldestKey = this.model.accessOrder.shift();
if (oldestKey) {
this.model.entries.delete(oldestKey);
}
}
this.model.entries.set(key, value);
this.model.accessOrder.push(key);
}
return { success: true, value: undefined };
}
private modelFind(key: string): CacheResult<any> {
if (this.model.entries.has(key)) {
return { success: true, value: this.model.entries.get(key) };
} else {
return { success: false, error: 'not_found' };
}
}
private modelFlush(): CacheResult<void> {
this.model.entries.clear();
this.model.accessOrder = [];
return { success: true, value: undefined };
}
checkConsistency(): boolean {
return this.model.entries.size === this.actualCache.size();
}
getModelSize(): number {
return this.model.entries.size;
}
}
ステートフルプロパティテストの実行
ステートフルテストでは、ランダムな操作シーケンスを生成し、モデルと実装の両方に適用する。
- 結果の一致: 成功/失敗が同じ、返り値が等しい
- 状態の整合性: サイズ制限が守られている
- 不変条件: LRUの原則が維持されている
test('LRU cache stateful properties', () => {
const maxSize = 5;
const commandGen = fc.oneof(
fc.record({
type: fc.constant('cache' as const),
key: fc.constantFrom('a', 'b', 'c', 'd', 'e', 'f', 'g'),
value: fc.integer()
}),
fc.record({
type: fc.constant('find' as const),
key: fc.constantFrom('a', 'b', 'c', 'd', 'e', 'f', 'g')
}),
fc.record({
type: fc.constant('flush' as const)
})
);
fc.assert(fc.property(
fc.array(commandGen, {maxLength: 50}),
(commands) => {
const tester = new CacheModelTester(maxSize);
for (const cmd of commands) {
const modelResult = tester.executeModelCommand(cmd);
const actualResult = tester.executeActualCommand(cmd);
if (modelResult.success !== actualResult.success) {
return false;
}
if (modelResult.success && actualResult.success) {
if (cmd.type === 'find' && modelResult.value !== actualResult.value) {
return false;
}
}
if (tester.getModelSize() > maxSize) {
return false;
}
if (!tester.checkConsistency()) {
return false;
}
}
return true;
}
));
});
並行操作のシミュレーション
並行環境でのキャッシュの振る舞いをテストする。
- バッチ操作: 複数のcache操作を連続実行
- 一貫性チェック: find操作で最新値が取得できるか検証
- LRUロジック: 容量制限で削除されたエントリを考慮
test('cache concurrent operations simulation', () => {
const maxSize = 3;
const concurrentCommandsGen = fc.tuple(
fc.array(fc.record({
type: fc.constant('cache' as const),
key: fc.constantFrom('x', 'y', 'z'),
value: fc.integer({min: 1, max: 100})
}), {maxLength: 10}),
fc.array(fc.record({
type: fc.constant('find' as const),
key: fc.constantFrom('x', 'y', 'z')
}), {maxLength: 10})
);
fc.assert(fc.property(
concurrentCommandsGen,
([cacheOps, findOps]) => {
const cache = new Cache(maxSize);
for (const op of cacheOps) {
cache.cache(op.key, op.value);
}
const expectedValues = new Map<string, number>();
for (const op of cacheOps.reverse()) {
if (!expectedValues.has(op.key)) {
expectedValues.set(op.key, op.value);
}
}
for (const op of findOps) {
const result = cache.find(op.key);
const expected = expectedValues.get(op.key);
if (expected !== undefined) {
if (!result.success || result.value !== expected) {
if (cache.size() === maxSize) {
continue;
} else {
return false;
}
}
}
}
return cache.size() <= maxSize;
}
));
});
長期実行テスト
長時間の操作シーケンスでもシステムが正常に動作することを検証する。
これにより、メモリリークやパフォーマンス劣化などの問題を発見できる。
test('cache long-running behavior', () => {
const maxSize = 10;
fc.assert(fc.property(
fc.array(
fc.oneof(
fc.record({
type: fc.constant('cache' as const),
key: fc.string({minLength: 1, maxLength: 5}),
value: fc.anything()
}),
fc.record({
type: fc.constant('find' as const),
key: fc.string({minLength: 1, maxLength: 5})
})
),
{minLength: 100, maxLength: 1000}
),
(commands) => {
const cache = new Cache(maxSize);
const keyValueHistory = new Map<string, any>();
for (const cmd of commands) {
if (cmd.type === 'cache') {
const result = cache.cache(cmd.key, cmd.value);
expect(result.success).toBe(true);
keyValueHistory.set(cmd.key, cmd.value);
if (cache.size() > maxSize) {
return false;
}
} else if (cmd.type === 'find') {
const result = cache.find(cmd.key);
if (result.success) {
const expectedValue = keyValueHistory.get(cmd.key);
if (result.value !== expectedValue) {
return false;
}
}
}
}
return true;
}
), {numRuns: 10});
});
第 10 章:ケーススタディ:書籍の貸出システム
概要
実際のデータベースを使用した書籍の貸出システムを題材として、ステートフルプロパティテストの実践的な適用方法を詳しく解説する。PostgreSQLを使用したより現実的なシステムでの結合テストの実装方法について紹介する。
システム要件
-
基本機能
- 書籍の登録(ISBN、タイトル、著者、所有冊数)
- 貸出処理(利用可能冊数の確認と更新)
- 返却処理(在庫数の更新)
- 書籍検索
-
ビジネスルール
- 利用可能冊数は所有冊数を超えない
- 利用可能冊数は負にならない
- 貸出中 + 利用可能 = 所有冊数
- 存在しない書籍は貸出・返却できない
データモデル
書籍情報は以下の属性を持ちます:
-
isbn
: 国際標準図書番号(一意識別子) -
title
: 書籍タイトル -
author
: 著者名 -
owned
: 所有冊数 -
available
: 利用可能冊数
データベーススキーマ
TypeScript entity 定義
interface Book {
isbn: string;
title: string;
author: string;
owned: number;
available: number;
}
class BookstoreDb {
private books: Map<string, Book> = new Map();
constructor() {}
async addBook(book: Omit<Book, 'available'>): Promise<void> {
const newBook: Book = {
...book,
available: book.owned
};
this.books.set(book.isbn, newBook);
}
async findBook(isbn: string): Promise<Book | null> {
return this.books.get(isbn) || null;
}
async borrowCopy(isbn: string): Promise<{success: boolean, error?: string}> {
const book = this.books.get(isbn);
if (!book) {
return {success: false, error: 'book_not_found'};
}
if (book.available <= 0) {
return {success: false, error: 'no_copies_available'};
}
book.available -= 1;
this.books.set(isbn, book);
return {success: true};
}
async returnCopy(isbn: string): Promise<{success: boolean, error?: string}> {
const book = this.books.get(isbn);
if (!book) {
return {success: false, error: 'book_not_found'};
}
if (book.available >= book.owned) {
return {success: false, error: 'all_copies_returned'};
}
book.available += 1;
this.books.set(isbn, book);
return {success: true};
}
async listBooks(): Promise<Book[]> {
return Array.from(this.books.values());
}
}
プロパティベーステストのアプローチ
1. ジェネレーターの設計
ISBNジェネレーター: ISBN-10とISBN-13の両形式に対応したリアルな番号を生成します。これにより、実際の書籍管理システムと同様のテストが可能になります。
書籍ジェネレーター: タイトル、著者名、所有冊数をランダムに生成します。現実的な制約(文字長制限、冊数の上限など)を考慮します。
ISBN生成器
const isbnGen = fc.oneof(
// ISBN-10形式
fc.tuple(
fc.integer({min: 0, max: 9999}).map(n => n.toString().padStart(4, '0')),
fc.integer({min: 0, max: 9999}).map(n => n.toString().padStart(4, '0')),
fc.integer({min: 0, max: 999}).map(n => n.toString().padStart(3, '0')),
fc.oneof(
fc.integer({min: 0, max: 9}).map(n => n.toString()),
fc.constant('X')
)
).map(([p1, p2, p3, check]) => `${p1}-${p2}-${p3}-${check}`),
// ISBN-13形式
fc.tuple(
fc.constantFrom('978', '979'),
fc.integer({min: 0, max: 9999}).map(n => n.toString().padStart(4, '0')),
fc.integer({min: 0, max: 9999}).map(n => n.toString().padStart(4, '0')),
fc.integer({min: 0, max: 999}).map(n => n.toString().padStart(3, '0')),
fc.integer({min: 0, max: 9}).map(n => n.toString())
).map(([prefix, p1, p2, p3, check]) => `${prefix}-${p1}-${p2}-${p3}-${check}`)
);
const bookGen = fc.record({
isbn: isbnGen,
title: fc.string({minLength: 1, maxLength: 256}),
author: fc.string({minLength: 1, maxLength: 256}),
owned: fc.integer({min: 0, max: 50})
});
test('ISBN generation format', () => {
fc.assert(fc.property(
isbnGen,
(isbn) => {
const isbn10Pattern = /^\d{4}-\d{4}-\d{3}-[\dX]$/;
const isbn13Pattern = /^(978|979)-\d{4}-\d{4}-\d{3}-\d$/;
return isbn10Pattern.test(isbn) || isbn13Pattern.test(isbn);
}
));
});
モデルベーステスト
モデルベーステストでは、理想的なシンプルな実装(モデル)と実際のシステムを比較する。コマンドパターンには以下を含む。
- addBook: 書籍の追加
- borrowCopy: 貸出処理
- returnCopy: 返却処理
- findBook: 書籍検索
正確なモデル実装
interface BookstoreModel {
books: Map<string, Book>;
}
type BookstoreCommand =
| { type: 'addBook', book: Omit<Book, 'available'> }
| { type: 'borrowCopy', isbn: string }
| { type: 'returnCopy', isbn: string }
| { type: 'findBook', isbn: string };
class BookstoreModelTester {
private model: BookstoreModel;
private actualDb: BookstoreDb;
constructor() {
this.model = { books: new Map() };
this.actualDb = new BookstoreDb();
}
async executeModelCommand(cmd: BookstoreCommand): Promise<any> {
switch (cmd.type) {
case 'addBook':
return this.modelAddBook(cmd.book);
case 'borrowCopy':
return this.modelBorrowCopy(cmd.isbn);
case 'returnCopy':
return this.modelReturnCopy(cmd.isbn);
case 'findBook':
return this.modelFindBook(cmd.isbn);
}
}
async executeActualCommand(cmd: BookstoreCommand): Promise<any> {
switch (cmd.type) {
case 'addBook':
return this.actualDb.addBook(cmd.book);
case 'borrowCopy':
return this.actualDb.borrowCopy(cmd.isbn);
case 'returnCopy':
return this.actualDb.returnCopy(cmd.isbn);
case 'findBook':
return this.actualDb.findBook(cmd.isbn);
}
}
private modelAddBook(book: Omit<Book, 'available'>): Promise<void> {
const newBook: Book = {
...book,
available: book.owned
};
this.model.books.set(book.isbn, newBook);
return Promise.resolve();
}
private modelBorrowCopy(isbn: string): Promise<{success: boolean, error?: string}> {
const book = this.model.books.get(isbn);
if (!book) {
return Promise.resolve({success: false, error: 'book_not_found'});
}
if (book.available <= 0) {
return Promise.resolve({success: false, error: 'no_copies_available'});
}
book.available -= 1;
this.model.books.set(isbn, book);
return Promise.resolve({success: true});
}
private modelReturnCopy(isbn: string): Promise<{success: boolean, error?: string}> {
const book = this.model.books.get(isbn);
if (!book) {
return Promise.resolve({success: false, error: 'book_not_found'});
}
if (book.available >= book.owned) {
return Promise.resolve({success: false, error: 'all_copies_returned'});
}
book.available += 1;
this.model.books.set(isbn, book);
return Promise.resolve({success: true});
}
private modelFindBook(isbn: string): Promise<Book | null> {
return Promise.resolve(this.model.books.get(isbn) || null);
}
checkConsistency(): boolean {
// モデルと実装の書籍数が一致するかチェック
return this.model.books.size === this.actualDb['books'].size;
}
}
貸出システムのステートフルテスト
test('bookstore stateful properties', () => {
const commandGen = fc.oneof(
// addBook command
fc.record({
type: fc.constant('addBook' as const),
book: bookGen
}),
// borrowCopy command
fc.record({
type: fc.constant('borrowCopy' as const),
isbn: isbnGen
}),
// returnCopy command
fc.record({
type: fc.constant('returnCopy' as const),
isbn: isbnGen
}),
// findBook command
fc.record({
type: fc.constant('findBook' as const),
isbn: isbnGen
})
);
fc.assert(fc.property(
fc.array(commandGen, {maxLength: 100}),
async (commands) => {
const tester = new BookstoreModelTester();
for (const cmd of commands) {
const modelResult = await tester.executeModelCommand(cmd);
const actualResult = await tester.executeActualCommand(cmd);
if (cmd.type === 'borrowCopy' || cmd.type === 'returnCopy') {
const modelRes = modelResult as {success: boolean, error?: string};
const actualRes = actualResult as {success: boolean, error?: string};
if (modelRes.success !== actualRes.success || modelRes.error !== actualRes.error) {
return false;
}
} else if (cmd.type === 'findBook') {
const modelBook = modelResult as Book | null;
const actualBook = actualResult as Book | null;
if (JSON.stringify(modelBook) !== JSON.stringify(actualBook)) {
return false;
}
}
if (!tester.checkConsistency()) {
return false;
}
}
return true;
}
), {numRuns: 50});
});
不変条件テスト
ビジネスロジックの不変条件をテストし、どのような操作シーケンスでも次の条件を常に満たすことを検証する。
- 利用可能冊数 ≤ 所有冊数
- 利用可能冊数 ≥ 0
- 貸出中冊数 + 利用可能冊数 = 所有冊数
test('bookstore business logic invariants', () => {
fc.assert(fc.property(
fc.array(
fc.oneof(
fc.record({
type: fc.constant('addBook' as const),
book: bookGen
}),
fc.record({
type: fc.constant('borrowCopy' as const),
isbn: isbnGen
}),
fc.record({
type: fc.constant('returnCopy' as const),
isbn: isbnGen
})
),
{maxLength: 50}
),
async (commands) => {
const db = new BookstoreDb();
const addedBooks = new Set<string>();
for (const cmd of commands) {
if (cmd.type === 'addBook') {
await db.addBook(cmd.book);
addedBooks.add(cmd.book.isbn);
} else if (cmd.type === 'borrowCopy') {
await db.borrowCopy(cmd.isbn);
} else if (cmd.type === 'returnCopy') {
await db.returnCopy(cmd.isbn);
}
const books = await db.listBooks();
for (const book of books) {
// 利用可能冊数 ≤ 所有冊数
if (book.available > book.owned) {
return false;
}
// 利用可能冊数 ≥ 0
if (book.available < 0) {
return false;
}
// 貸出中冊数 + 利用可能冊数 = 所有冊数
if (book.owned < 0) {
return false;
}
}
}
return true;
}
), {numRuns: 100});
});
同時借出シミュレーション
複数のユーザーが同時に借出リクエストを行うケースをシミュレートし、競合状態でもシステムが正しく動作することを確認する。
test('concurrent borrowing simulation', () => {
fc.assert(fc.property(
fc.record({
books: fc.array(bookGen.filter(book => book.owned > 0), {minLength: 1, maxLength: 5}),
borrowRequests: fc.array(
fc.record({
isbn: isbnGen,
userId: fc.string({minLength: 1, maxLength: 10})
}),
{maxLength: 50}
)
}),
async ({books, borrowRequests}) => {
const db = new BookstoreDb();
for (const book of books) {
await db.addBook(book);
}
const bookIsbnSet = new Set(books.map(b => b.isbn));
const successfulBorrows = new Map<string, number>();
for (const request of borrowRequests) {
if (!bookIsbnSet.has(request.isbn)) continue;
const result = await db.borrowCopy(request.isbn);
if (result.success) {
const currentCount = successfulBorrows.get(request.isbn) || 0;
successfulBorrows.set(request.isbn, currentCount + 1);
}
}
for (const book of books) {
const borrowedCount = successfulBorrows.get(book.isbn) || 0;
if (borrowedCount > book.owned) {
return false;
}
const dbBook = await db.findBook(book.isbn);
if (!dbBook) return false;
if (dbBook.available + borrowedCount !== book.owned) {
return false;
}
}
return true;
}
));
});
第 11 章:有限状態機械プロパティ
システムを有限状態機械としてモデル化できる場合の、ステートフルプロパティのより高度な活用方法について解説されている。サーキットブレーカーパターンを実例として、状態に応じたコマンド生成と検証の手法を詳しく紹介されている。
サーキットブレーカーの実装
サーキットブレーカーは、システムの過負荷やエラー連発時にサービスを一時的に遮断し、システム全体の安定性を保つ仕組み。主には「正常」「遮断」「半開」「ブロック」の状態を持つ。
export type CircuitBreakerState = 'unregistered' | 'ok' | 'tripped' | 'blocked';
export type CircuitError = 'badarg' | 'badmatch' | 'badarith' | 'whatever' | 'timeout' | 'not_found';
export type IgnoredError = 'ignore1' | 'ignore2';
export interface CircuitBreakerOptions {
nError: number;
timeError: number;
nTimeout: number;
timeTimeout: number;
nCallTimeout: number;
timeCallTimeout: number;
ignoreErrors: IgnoredError[];
}
export const DEFAULT_OPTIONS: CircuitBreakerOptions = {
nError: 3,
timeError: 300000,
nTimeout: 3,
timeTimeout: 300000,
nCallTimeout: 3,
timeCallTimeout: 300000,
ignoreErrors: ['ignore1', 'ignore2']
};
export type CircuitResult<T> =
| { success: true; value: T }
| { success: false; error: 'circuit_breaker'; reason: string };
export class MockCircuitBreaker {
private internalState: {
state: CircuitBreakerState;
errors: number;
timeouts: number;
callTimeouts: number;
lastErrorTime: number;
lastTimeoutTime: number;
lastCallTimeoutTime: number;
options: CircuitBreakerOptions;
};
constructor(options: Partial<CircuitBreakerOptions> = {}) {
this.internalState = {
state: 'unregistered',
errors: 0,
timeouts: 0,
callTimeouts: 0,
lastErrorTime: 0,
lastTimeoutTime: 0,
lastCallTimeoutTime: 0,
options: { ...DEFAULT_OPTIONS, ...options }
};
}
call<T>(fn: () => T): CircuitResult<T> {
if (this.internalState.state === 'unregistered') {
this.internalState.state = 'ok';
}
if (this.internalState.state === 'tripped' || this.internalState.state === 'blocked') {
return {
success: false,
error: 'circuit_breaker',
reason: `Circuit breaker is ${this.internalState.state}`
};
}
try {
const result = fn();
this.onSuccess();
return { success: true, value: result };
} catch (error) {
if (error instanceof Error) {
const errorType = error.message as CircuitError | IgnoredError;
if (this.internalState.options.ignoreErrors.includes(errorType as IgnoredError)) {
this.onSuccess();
return { success: false, error: 'circuit_breaker', reason: errorType };
}
if (errorType === 'timeout') {
this.onTimeout();
return { success: false, error: 'circuit_breaker', reason: 'timeout' };
}
this.onError();
return { success: false, error: 'circuit_breaker', reason: errorType };
}
this.onError();
return { success: false, error: 'circuit_breaker', reason: 'unknown_error' };
}
}
manualBlock(): void {
this.internalState.state = 'blocked';
}
manualDeblock(): void {
if (this.internalState.state === 'blocked') {
this.internalState.state = 'ok';
this.resetCounters();
}
}
manualReset(): void {
this.internalState.state = 'ok';
this.resetCounters();
}
getState(): CircuitBreakerState {
return this.internalState.state;
}
private onSuccess(): void {
if (this.internalState.state === 'ok') {
if (this.internalState.errors > 0) {
this.internalState.errors--;
} else if (this.internalState.timeouts > 0) {
this.internalState.timeouts--;
}
}
}
private onError(): void {
if (this.internalState.state === 'ok') {
this.internalState.errors++;
this.internalState.lastErrorTime = Date.now();
if (this.internalState.errors >= this.internalState.options.nError) {
this.internalState.state = 'tripped';
}
}
}
private onTimeout(): void {
if (this.internalState.state === 'ok') {
this.internalState.timeouts++;
this.internalState.lastTimeoutTime = Date.now();
if (this.internalState.timeouts >= this.internalState.options.nTimeout) {
this.internalState.state = 'tripped';
}
}
}
private resetCounters(): void {
this.internalState.errors = 0;
this.internalState.timeouts = 0;
this.internalState.callTimeouts = 0;
}
}
FSMモデル
有限状態機械(FSM)プロパティテストではシステムの状態遷移を数学的にモデル化し、そのモデルに対して実装の振る舞いを検証する。
export interface CircuitBreakerModelState {
state: CircuitBreakerState;
errors: number;
timeouts: number;
limit: number;
}
export function initialCircuitModelState(): CircuitBreakerModelState {
return {
state: 'unregistered',
errors: 0,
timeouts: 0,
limit: 3
};
}
export function transitionToOk(state: CircuitBreakerModelState): CircuitBreakerModelState {
return {
...state,
state: 'ok'
};
}
export function addError(state: CircuitBreakerModelState): CircuitBreakerModelState {
const newErrors = state.errors + 1;
return {
...state,
errors: newErrors,
state: newErrors >= state.limit ? 'tripped' : state.state
};
}
export function addTimeout(state: CircuitBreakerModelState): CircuitBreakerModelState {
const newTimeouts = state.timeouts + 1;
return {
...state,
timeouts: newTimeouts,
state: newTimeouts >= state.limit ? 'tripped' : state.state
};
}
export function decreaseErrorCount(state: CircuitBreakerModelState): CircuitBreakerModelState {
if (state.errors > 0) {
return { ...state, errors: state.errors - 1 };
} else if (state.timeouts > 0) {
return { ...state, timeouts: state.timeouts - 1 };
}
return state;
}
export function resetState(state: CircuitBreakerModelState): CircuitBreakerModelState {
return {
...state,
state: 'ok',
errors: 0,
timeouts: 0
};
}
export function blockState(state: CircuitBreakerModelState): CircuitBreakerModelState {
return {
...state,
state: 'blocked'
};
}
FSM操作ジェネレーター
type CircuitOperation =
| { type: 'success' }
| { type: 'error', errorType: CircuitError }
| { type: 'ignored_error', errorType: IgnoredError }
| { type: 'timeout' }
| { type: 'manual_block' }
| { type: 'manual_deblock' }
| { type: 'manual_reset' };
const circuitOperationGen = fc.oneof(
fc.record({ type: fc.constant('success' as const) }),
fc.record({
type: fc.constant('error' as const),
errorType: fc.constantFrom('badarg', 'badmatch', 'badarith', 'whatever', 'not_found') as fc.Arbitrary<CircuitError>
}),
fc.record({
type: fc.constant('ignored_error' as const),
errorType: fc.constantFrom('ignore1', 'ignore2') as fc.Arbitrary<IgnoredError>
}),
fc.record({ type: fc.constant('timeout' as const) }),
fc.record({ type: fc.constant('manual_block' as const) }),
fc.record({ type: fc.constant('manual_deblock' as const) }),
fc.record({ type: fc.constant('manual_reset' as const) })
);
状態遷移テスト
test('circuit breaker FSM properties', () => {
fc.assert(fc.property(
fc.array(circuitOperationGen, {maxLength: 50}),
(operations) => {
const breaker = new MockCircuitBreaker();
let modelState = initialCircuitModelState();
for (const op of operations) {
const previousState = breaker.getState();
try {
switch (op.type) {
case 'success':
breaker.call(() => 'success');
if (modelState.state === 'unregistered') {
modelState = transitionToOk(modelState);
}
if (modelState.state === 'ok') {
modelState = decreaseErrorCount(modelState);
}
break;
case 'error':
breaker.call(() => { throw new Error(op.errorType); });
if (modelState.state === 'unregistered') {
modelState = transitionToOk(modelState);
}
if (modelState.state === 'ok') {
modelState = addError(modelState);
}
break;
case 'ignored_error':
breaker.call(() => { throw new Error(op.errorType); });
if (modelState.state === 'unregistered') {
modelState = transitionToOk(modelState);
}
if (modelState.state === 'ok') {
modelState = decreaseErrorCount(modelState);
}
break;
case 'timeout':
breaker.call(() => { throw new Error('timeout'); });
if (modelState.state === 'unregistered') {
modelState = transitionToOk(modelState);
}
if (modelState.state === 'ok') {
modelState = addTimeout(modelState);
}
break;
case 'manual_block':
breaker.manualBlock();
modelState = blockState(modelState);
break;
case 'manual_deblock':
breaker.manualDeblock();
if (modelState.state === 'blocked') {
modelState = resetState(modelState);
}
break;
case 'manual_reset':
breaker.manualReset();
modelState = resetState(modelState);
break;
}
} catch (error) {
// Check if the model and implementation states match even when errors occur
}
if (breaker.getState() !== modelState.state) {
return false;
}
}
return true;
}
));
});
前提条件とアクション後状態のテスト
test('circuit breaker preconditions and postconditions', () => {
fc.assert(fc.property(
circuitOperationGen,
(operation) => {
const breaker = new MockCircuitBreaker();
expect(breaker.getState()).toBe('unregistered');
if (operation.type === 'success') {
const result = breaker.call(() => 'test');
// 事後条件: 最初の操作後は'ok'状態になる
expect(breaker.getState()).toBe('ok');
expect(result.success).toBe(true);
} else if (operation.type === 'error') {
const result = breaker.call(() => { throw new Error(operation.errorType); });
// 事後条件: エラー後も'ok'状態(まだ閾値に達していない)
expect(breaker.getState()).toBe('ok');
expect(result.success).toBe(false);
} else if (operation.type === 'manual_block') {
breaker.manualBlock();
// 事後条件: 手動ブロック後は'blocked'状態
expect(breaker.getState()).toBe('blocked');
}
return true;
}
));
});
閾値テスト
test('circuit breaker threshold behavior', () => {
const errorLimit = 3;
const breaker = new MockCircuitBreaker({ nError: errorLimit });
for (let i = 0; i < errorLimit - 1; i++) {
const result = breaker.call(() => { throw new Error('badarg'); });
expect(result.success).toBe(false);
expect(breaker.getState()).toBe('ok');
}
const finalResult = breaker.call(() => { throw new Error('badarg'); });
expect(finalResult.success).toBe(false);
expect(breaker.getState()).toBe('tripped');
const blockedResult = breaker.call(() => 'should not execute');
expect(blockedResult.success).toBe(false);
expect(blockedResult.error).toBe('circuit_breaker');
expect(breaker.getState()).toBe('tripped');
});
回復動作テスト
test('circuit breaker recovery behavior', () => {
const breaker = new MockCircuitBreaker({ nError: 2 });
breaker.call(() => { throw new Error('badarg'); });
breaker.call(() => { throw new Error('badarg'); });
expect(breaker.getState()).toBe('tripped');
breaker.manualReset();
expect(breaker.getState()).toBe('ok');
const result = breaker.call(() => 'recovered');
expect(result.success).toBe(true);
expect(result.value).toBe('recovered');
});
test('circuit breaker gradual recovery', () => {
const breaker = new MockCircuitBreaker({ nError: 3 });
breaker.call(() => { throw new Error('badarg'); });
breaker.call(() => { throw new Error('badarg'); });
expect(breaker.getState()).toBe('ok');
breaker.call(() => 'success');
breaker.call(() => { throw new Error('badarg'); });
breaker.call(() => { throw new Error('badarg'); });
expect(breaker.getState()).toBe('ok');
breaker.call(() => { throw new Error('badarg'); });
expect(breaker.getState()).toBe('tripped');
});
おわりに
この本を読むまでプロパティベーステストという手法そのものを知りませんでした。
正直なところ、今はプロダクトのテストコードは要件を満たす特定のパターンしかテスト出来ていなかったりそもそもテストを書けていなかったします。また、テストを増やしたいけど増やしすぎると後の管理が面倒なのでどの程度テストを書くべきかメンバーと相談しているところでした。
これらの一部にプロパティベーステストを採用することで、テストコードを肥大化させずにエッジケースの検出を容易に出来るのではと期待しているので、まずはマイクロサービスのテストをプロパティベーステストで書いてみて効果を計測してみようと思います。皆さんも良いテストライフを。
Discussion