вторник, 28 февраля 2012 г.

Принцип замещения Лисков и контракты

Идея этой заметки навеяна статьей Александра Бындю “Дополнение к LSP” и может рассматриваться, как развернутый комментарий к статье Александра.

Итак, вопрос следующий, предположим, один из членов команды пытается реализовать интерфейс IList of T в классе DoubleList of T таким образом, чтобы при добавлении элемента с помощью метода Add, добавлялся бы не один, а два одинаковых элемента. Поскольку класс List of T всегда добавляет только один элемент, то можно считать, что данное поведение нарушает принцип замещения Лисков (LSP – Liskov Substitution Principle).

UPDATE: Если вы вначале хотите познакомиться с определением принципа замещения Лисков, то оно приведено в конце статьи в разделе “Принцип замещения Лисков. Определение”.

Теперь давайте рассмотрим, так ли это, если речь идет о платформе .NET, ну и вообще поговорим о том, можем ли мы утверждать, что метод нарушает принцип замещения Лисков при отсутствии формальной спецификации того, что этот метод должен делать.

Для начала нужно внести небольшую правку в условие задачи (да, я понимаю, что это не честно, но в данном случае это оправдано). В исходной задаче говорилось о реализации классом DoubleList интерфейса IList of T, однако на самом деле в .NET Framework метод Add объявлен в интерфейсе ICollection of T, а значит, следует рассматривать, нарушает ли класс DoubleList of T контракт коллекции, а не списка.

ПРИМЕЧАНИЕ
Для простоты чтения кода и запуска примеров, я буду использовать не обобщенную версию класса DoubleList, а специализированный контейнер для хранения строк, т.е. по сути, наш DoubleList будет реализовать интерфейс ICollection of string.

public class DoubleList : ICollection<string>
{
   
private readonly List<string> _backingList = new List<string
>();

   
public void Add(string
item)
    {
       
// Вместо добавления элемента один раз, добавляем его 2 раза
        _backingList.Add(item);
        _backingList.Add(item);
    }

   
// Остальные методы не важны
}

Теперь, предположим, что где-то в коде мы используем интерфейс ICollection of string (т.е. имеем полиморфное использование) и рассчитываем на то, что количество элементов увеличится строго на один. Подобное поведение можно выразить либо с помощью формального постусловия (например, с использованием Code Contract), либо можно выразить в виде юнит-теста. Поскольку к контрактам мы перейдем позже, то давайте рассмотрим вначале юнит-тест:

[Test]
public void
TestAddMethodAddsOnlyOneElement()
{
   
ICollection<string> collection = new DoubleList
();
   
int
oldCount = collection.Count;

    collection.Add(
"foo"
);
   
Assert.That(collection.Count, Is.EqualTo(oldCount + 1));
}

Да, действительно, этот тест будет нормально работать при использовании в качестве объекта collection List of string, и будет падать в случае использования DoubleList.

Но вот только один вопрос: а вправе ли мы ожидать от метода Add интерфейса ICollection of T именно такого поведения? Когда речь заходит о корректности (проще говоря, о том, баг это или нет, причем не важно, где: в коде или дизайне), то она определяется лишь тем, соответствует ли поведение кода спецификации или нет. Спецификация может быть формальной или не формальной, но программа некорректна лишь тогда, когда она перестает делать то, для чего она предназначена, а если никто не знает, для чего она предназначена, то уже никто не может сказать, что она работает не правильно.

Некоторое выражение, такое как x = y / 2, само по себе не является ни корректным, ни не корректным. Все зависит от того, каким должно быть отношение между x и y (подробнее об этом см. “Проектирование по контракту. Корректность ПО”). Ситуация с методом Add аналогична: без формального или хотя бы неформального описания того, что должен делать этот метод мы не может утверждать правильно ли он реализован наследником. Если же мы откроем официальную документацию для ICollection (Of T).Add Method, то все что мы увидим, это одну строчку, в которой будет сказано, что этот метод добавляет элемент в коллекцию. При этом все остальное (например, а точно ли он будет добавлен или в каком количестве), это лишь наши с вами допущения и единственное, что можно сделать, это постараться выяснить, как ведут себя другие реализации интерфейса ICollection of T.

Давайте добавим следующий тест, но на этот раз, будем проверять, что добавление двух одинаковых элементов, будет увеличивать количество элементов на 2. Понятное дело, что это более частный случай, по сравнению с добавлением одного элемента, но ведь, опять-таки, если вернуться к документации метода Add, то там ни слова не говорится о том, что мы не можем добавлять одинаковые элементы; единственным ограничением является то, чтобы мы не добавляли элементы в коллекцию только для чтения. Других предусловий (в официальной документации они обычно выражаются в виде исключений) документация не содержит, а значит и никаких других проверок перед вызовом метода Add делать не нужно:

[TestCaseSource("GetAllCollections")]
public void TestAddToCollectionTwiceAddsTwoElement(ICollection<string
> collection)
{
   
int
oldCount = collection.Count;
   
if
(collection.IsReadOnly)
    {
       
Console.WriteLine("Current collection type ({0}) is readonly. Skipping it..."
,
        collection.GetType());
       
return
;
    }

    collection.Add(
"foo"
);
    collection.Add(
"foo"
);
   
Assert.That(collection.Count, Is.EqualTo(oldCount + 2));
}

Еще раз обращаю внимание на проверку предусловия метода Add, контракты – это не игра в одни ворота, поэтому мы должны выполнять свою часть договора, чтобы вызываемый код выполнял свою. Сам тест, является параметризованным (из состава NUnit), входные значения которого будут браться из метода GetAllCollections. Я не будут заморачиваться с поиском всех существующих классов, реализующих интерфейс ICollection of T, а просто добавлю некоторые популярные типы коллекций вручную:

private static ICollection<string>[] GetAllCollections()
{
   
return new ICollection<string
>[]
                {
                   
new List<string
>(),
                   
new HashSet<string
>(),
                   
new Collection<string
>(),
                   
new BindingList<string
>(),
                   
new LinkedList<string
>(),
                   
new ObservableCollection<string
>(),
                   
new ReadOnlyCollection<string>(new List<string
>()),
                   
new SortedSet<string
>(),
                   
new string[]{},
                };
}

Теперь запускаем приведенный выше тест и видим, что как минимум два типа коллекций добавляют лишь один элемент, хотя мы просили добавить два. Это, конечно же, типы коллекций, которые не позволяют хранить дубликаты, такие как HashSet of T и SortedSet of T.

А теперь давайте вернемся к исходному вопросу: нарушает ли реализация метода Add классом DoubleList принцип замещения Лисков? Ответ: Нет, не нарушает!

Метод Add интерфейса ICollection of T не налагает никаких ограничений на то, какое количество элементов будет в коллекции после добавления, а значит, мы не можем требовать от всех классов, реализующих этот интерфейс, следовать определенному правилу. На самом деле, более правдоподобным (исходя из поведения коллекций, реализующих ICollection of T) является следующее постусловие: после вызова метода Add, следующий за ним вызов метода Contains должен вернуть true и количество элементов коллекции не должно уменьшиться (т.е. newCount >= oldCount).

В таком случае, если в нашем тесте заменить существующее утверждение на:

Assert.IsTrue(collection.Contains("foo"));

то все тесты будут проходить успешно.

Заключение

Можно смело говорить о том, что DoubleList не нарушает принцип замещения Лисков, либо нарушает вместе с некоторыми стандартными классами коллекций из BCL. С другой стороны, я согласен, что дизайн класса DoubleList «кривоват», но не из-за нарушения некоторого принципа, понять формулировку которого в здравом уме практически невозможно (*), я бы скорее апеллировал к тому, что подобное поведение является интуитивно не понятным и наверняка приведет к проблемам в сопровождении.

Не зря Мейер в своей толстенной книге (см. доп. ссылки) столь важную роль отводит формальной спецификации программ с помощью утверждений (предусловий, постусловий и инвариантов). Именно отсутствие формального описания того, что должен делать метод делает таким сложным написания наследника, который бы работал «правильно», поскольку что такое «правильно», никто сказать не может. Сигнатура метода (и возможный комментарий) являются слишком неформальными, чтобы понять «изменится ли поведение при использовании наследника вместо базового класса».

В следующий раз мы посмотрим, как Code Contracts (поддержка которых частично включена в состав mscorlib) могут помочь в решении нашей задачи, и о том, какое же формальное постусловие есть у метода Add.

-------------------------

(*) Я отойду от обычного правила оформление сноски прямо в тексте и сделаю отдельный подраздел, посвященный определению принципа замещения Лисков.

Принцип замещения Лисков. Определение

В замечательной книге Джеймса Коплиена «Программирование на языке С++» дается отличное, и совершенно непонятное определение принципа замещения Лисков:

...если для каждого объекта o1 типа S существует объект o2 типа T такой, что для всех программ P, определенных в терминах T, поведение P не изменяется при замене o2 на o1, то S является подтипом (subtype) для T.

(If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2  then S is a subtype of T.)

В целом, все хорошо, за исключением того, что совершенно не понятно, что означает «в контексте Т» и совсем не понятно, что означает, «поведение P не изменится», когда это самое поведение нигде не описано.

Другое популярное, но не более понятное определение, можно найти в книге Боба Мартина:

Должна быть возможность вместо базового типа подставить любое его подтип.

Это определение проще, но едва ли яснее. В любом объектно-ориентированном языке программирования, существует неявное преобразование от наследника к базовому классу (при учете использования открытого наследования), таким образом, это требование стоит отнести скорее к компилятору или языку программированию, а не к классам определяемым пользователям. Сам Мартин в своей книге (а также в статье The Liskov Substituion Principle) говорит о важности контрактов, и в частности, о важности предусловий и постусловий для спецификации поведения виртуальных методов.

Контракты – это и есть та самая возможность спецификации поведения P, о котором говорится в исходном определении, и именно благодаря этой спецификации мы сможем гарантировать (или хотя бы понять), что поведение наследника соответствует поведению базового класса или интерфейса.

Дополнительные ссылки

20 комментариев:

  1. А мне кажется, что в дизайне DoubleList всё в порядке. В твоём тесте TestAddMethodAddsOnlyOneElement, ты тестируешь вроде бы ICollection, но на самом деле это не так. Так как тест ожидает, что при добавлении 1 элемента суммарное количество элементов увеличится на 1, то он тестирует конкретные реализации ICollection, у которых это должно выполняться. В чем полезность этого теста? В том, что если бизнес логика рассчитана только на те коллекции, которые проходят этот тест, то никакой умник уже не добавит DoubleList.

    ОтветитьУдалить
  2. Артем, так я же и пишу о том, что с точки зрения стандартных контейнеров .net framework с классом DoubleList все в полном порядке. Он ничего не нарушает, поскольку от него ничего подобного не требуется.

    Моим первым тестом я лишь показываю, что такое требование к коллекции (что она обязательно добавляет в точности один элемент) некорректно, поскольку ему не следуют другие стандартные коллекции.

    ОтветитьУдалить
  3. Ну мы сейчас разведем такой же холивар, как и в блоге Александра Бындю :). Я хочу сказать, что тут не всё так просто. Первый тест - он корректный с точки зрения того, что если на этом завязана логика и кто-то в эту логику добавит DoubleList, то тест сразу же скажет, что DoubleList не подходит под требования к приложению. Но с другой стороны - в тесте от коллекции ожидается какое то конкретное поведение, которое не обязано быть в объекте, реализующем коллекцию. То есть с одной стороны тест как бы помогает логике и не пускает туда ничего, что не удовлетворяет условию в тесте, но с другой стороны это ограничивает разработчика в реализации интерфейса коллекции. Тут есть и плюсы и минусы, и об этом можно долго спорить. Я считаю, что если для автора системы этот вопрос принципиален, то он должен ввести какую то абстракцию в виде интерфейса (или абстрактного класса) с явным указанием предусловий и постусловий и проверкой их в тесте. То есть чтобы тест работал с каким нибудь ISingleList или чтото типа того. В этом случае DoubleList уже нельзя будет наследовать от ISingleList и это будет ясно как с точки зрения проектирования, также будет и понятно разработчику. Я, собственно, поэтому и написал Саше, что пример не очень удачный, так как необходимо рассматривать не метод Add класса DoubleList и не тот факт, что DoubleList реализует список или коллекцию. Нужно рассматривать архитектуру системы вцелом, как тестов в этом посте или примера кода у Саши. А ты пишешь "дизайн класса DoubleList «кривоват»" - я вот с этим, собственно, и не согласен. Кривоват не только дизайн этого класса, но и дизайн всей логики, что использует ICollection вместо ISingleList.

    ОтветитьУдалить
  4. Артем: сразу скажу по поводу того, что мне кажется "кривоватым" (сразу оговорюсь, я контекста задачи не знаю, поэтому сильно настаивать не буду).

    Идея постоянного добавления в методе Add двух элементов вместо одного кажется сомнительной. Ведь если мы точно знаем, что в новой коллекции всегда находится по два одинаковых элемента, то можно в список всегда добавлять один элемент и нужную логику по "дублированию" перенести на сторону клиента (т.е. удваивать количество элементов уже после нахождения нужного элемента или в процессе итерирования коллекции). Если такое решение не подходит и есть четкий бизнес-рул, который бы говорил, зачем нам нужно удваивать трудозатраты по памяти и по поиску, ну что же, возможно такой кейс и правда существует.

    Теперь по поводу тестов. Александр в своем посте выразил мысль, что поведение DoubleList-а нарушает принцип LSP, определение которого дано и у Саши, и у меня. А я в этом посте пытаюсь показать, что никакого нарушения нет, поскольку нет никаких причин полагать, что метод Add коллекции обязан добавлять новый элемент и не может добавлять два элемента вместо одного (посколкьу есть коллекции, которые в некоторых случаях вовсе ничего не добавляют в коллекцию).

    Мои тесты - это лишь попытка показать "клиента" класса, рассчитывающего на некоторое "согласованное" поведение всех реализаций класса ICollection и попытка вывести то "общее поведение", которое присуще всем коллекциям, на которое может расчитывать клиент этого интерфейса и которому должны следовать все реализации.

    ОтветитьУдалить
  5. Большое спасибо за пост.
    Когда мы с коллегами решали эту проблему, не смогли так формально определить, нарушается ли LSP или нет. Но мы тоже пришли к такому же выводу - DoubleList интуитивно непонятен.

    ОтветитьУдалить
  6. Мурад: Нарушение принципа LSP проще всего сформулировать так:

    "Производный класс нарушает принцип замещения Лисков, если один из его виртуальных методов не выполняет постусловие базового класса."

    З.Ы. Как я и написал в этой заметке, в следующий раз еще помучаю читателей принципом замещения, но на этот раз на примере Code Contracts.

    ОтветитьУдалить
  7. Я бы сказал, это просто способ нарушения LSP. Не берусь утверждать, что он единственный.

    ОтветитьУдалить
  8. Да, конечно, нужно небольшое уточнение.

    LSP будет нарушен, еще в одном случае: если наследник не будет соблюдать предусловие метода.

    З.Ы. Есть ли еще способы нарушения LSP, я не знаю. Ведь ключевым моментом этого принципа является "сохранение поведения P", а любое поведение метода может быть выражено в терминах предусловий и постусловий (т.е. что он ожидает от вызывающего кода и что делает в результате).

    ОтветитьУдалить
  9. Имхо конечно, но главная мысль, которая впрочем не следует из содержания статьи, заключена в последнем абзаце перед заключением. Можно было бы оставить вступление, чтобы было понятно где источник "холивара", указанный абзац и заключение.

    ОтветитьУдалить
  10. А, по-моему, все хорошо написано. Компиляторы обеспечивают возможность поместить вместо переменной базового типа переменную типа наследника, а так как ни один компилятор пока еще не научился анализировать логику кода, то это нужно проверять с помощью Code Contracts. Ждем продолжения :-)

    ОтветитьУдалить
  11. @kepka: продолжение будет. Есть мысли как минимум на две статьи; первая из них должна быть в понедельник-вторник. Вторая, думаю, в четверг.

    ОтветитьУдалить
  12. Думаю, DoubleList, все же, нарушает LSP.
    При наследовании от ICollection интерфейс IList неявно накладывает дополнительные ограничения на поведение наследуемых методов, включая Add и свойство Count (ничто не запрещает ему добавлять эти постусловия - все по LSP).
    А класс HashSet реализует ICollection (плюс ISet в .net 4), но не IList.

    ОтветитьУдалить
  13. "речь идет о платформе .NET" - хорошее замечание кстати. Потому что если говорить о Java, то для интерфейсов Collection и List контракты описаны очень внятно.

    ОтветитьУдалить
  14. @Мурадов Мурад: Да, совершенно согласен. Проблемы именно в интерфейсах BCL.

    ОтветитьУдалить
  15. "Является следующее предусловие": предусловие нужно заменить на "постусловие"

    ОтветитьУдалить
  16. Опечатка: любое его подтип

    ОтветитьУдалить
  17. Опечатка: сложным написания наследника => сложным написание наследника

    ОтветитьУдалить
  18. поскольку что такое => поскольку, что такое

    ОтветитьУдалить
  19. Этот комментарий был удален автором.

    ОтветитьУдалить
  20. Я бы переделал описание принципа Лисков, убрав банальности о приведении типов и сделав акцент именно на сохранении контракта. Тут же хорошо в качестве иллюстрации привести пример с тестами: любой класс должен проходить тесты своего базового класса.

    ОтветитьУдалить