2013-05-31

Тестирование файловой системы

Симуляция реального мира в песочнице
Май выдался богатым на новую и полезную информацию по тестированию: цикл статей от Сергея Теплякова, интересное обсуждение в Радио-Т.

В это же время появилась интересная задача связанная с доступом к файловой системе. Алгоритм:
1. получаем список файлов
2. каким-то образом фильтруем
3. обрабатываем отфильтрованные файлы.

Работа с ФС (по крайней мере в 6-й java) сосредоточена в классе File: list, delete, работа с путями. По сути эти методы относятся к сервису. Хочется иметь интерфейс чтобы убрать зависимость и получить возможность для подмены реализации, ну или хотя бы подмены mock-ами для тестирования.

Конечно можно выйти из положения, создавая нужную иерархию в определенном месте файловой системы и работать с настоящим доступом, но что, если хочется просто протестировать алгоритм.

Постановка задачи

По заданному пути
удалить пять файлов
с учетом сортировки по возрастанию
имя которых начинается с цифр
содержащие первой строкой ШИББОЛЕТ.

Решение

Реализация находится здесь, тесты здесь.

Сервис

FileService представляет собой фактически обертку с некоторыми удобными методами

public class FileService {
    /**
     * Get files in path
     */
    public Collection dir(File path) {
        return Arrays.asList(path.listFiles());
    }

    /**
     * Delete path
     */
    public void delete(File file) {
        if (!file.delete()) {
            log.debug("Cannot delete " + file.getPath());
        }
    }

    /**
     * Open file
     */
    public InputStream openStream(File path) throws FileNotFoundException {
        return new FileInputStream(path);
    }

    public Reader openReader(File path) throws FileNotFoundException {
        return new FileReader(path);
    }

    public boolean isDir(File path) {
        return path.isDirectory();
    }
}

Фильтрация

Фильтрация осуществляется при помощи удобнейшего FluentIterable:

public static Iterable filter(FileService fileService, File dir, int count, String mask, String prefix) {
        return FluentIterable
                .from(Ordering.natural().immutableSortedCopy(fileService.dir(dir)))
                .filter(new NamePredicate(mask))
                .filter(new ContentPredicate(fileService, prefix))
                .limit(count)
                .toImmutableList();
    } 

И пары предикатов для фильтрации по имени и содержимому. В предикат фильтрации по содержимому передается сервис файловой системы, плюс в Java 7 можно использовать очень удобный try для работы с Closeable ресурсами:
public class ContentPredicate implements Predicate {
    private FileService fileService;
    private String prefix;

    public ContentPredicate(FileService fileService, String prefix) {
        this.fileService = fileService;
        this.prefix = prefix;
    }

    @Override
    public boolean apply(@Nullable File file) {
        try (BufferedReader br = new BufferedReader(fileService.openReader(file))) {
            return prefix.equals(br.readLine());
        } catch (IOException ioe) {
            ContentPredicate.log.debug("Cannot read file " + file);
        }
        return false;
    }
}

Тестирование

С помощью mockito подменяем возвращаемые значения при тестировании предикатов и фильтра. Сами тесты получаются очень простыми и быстрыми:

@Test
    public void FilterTest() throws FileNotFoundException {
        FileService fileService = Mockito.mock(FileService.class);
        File dir = new File("/test/dir");
        List files = Arrays.asList(
                new File(dir, "100file.name"), // 0
                new File(dir, "bl"), // 1
                new File(dir, "099file.name"), // 2
                new File(dir, "bla"), // 3
                new File(dir, "098file.name"), // 4
                new File(dir, "blah"), // 5
                new File(dir, "097file.name")); // 6
        Mockito.when(fileService.dir(dir)).thenReturn(files);
        Mockito.when(fileService.openReader(files.get(6))).thenReturn(new StringReader("TEST"));
        Mockito.when(fileService.openReader(files.get(4))).thenReturn(new StringReader("TEST"));
        Mockito.when(fileService.openReader(files.get(2))).thenReturn(new StringReader("!!!!"));
        Mockito.when(fileService.openReader(files.get(0))).thenReturn(new StringReader("TEST"));

        Iterable result = Application.filter(fileService, dir, 3, "^\\d+.*$", "TEST");
        Iterator i = result.iterator();
        Assert.assertEquals(files.get(6), i.next());
        Assert.assertEquals(files.get(4), i.next());
        Assert.assertEquals(files.get(0), i.next());
        Assert.assertFalse(i.hasNext());
    }

Итог

Из минусов: имеется обертка, которая нужна лишь для тестирования "DIP головного мозга". Плюсы: классы становятся простыми и легко модифицируемым, самая важную логику становится легко тестировать.

2013-05-26

Экипировка к походу

В этом году планируется совершить несколько походов, поэтому активно озаботился экипировкой.

2013-05-25

Управление по Макиавелли

Не помню когда скачал, и даже не помню откуда (но раз скачал, значит источник был авторитетным). Закинул на телефон, чтобы слушать в дороге. У Тарасова очень своеобразная манера рассказывать, но если не заострять на этом внимание то можно слушать не напрягаясь. Государь гораздо более современный и близкий к нашему времени, чем Сун Цзы, чем и актуален.

2013-05-23

Клуб весёлых радиолюбителей

Устроили с Иваном на работе радиотехническую мастерскую, в качестве верстака применяли блин от штанги на пять кило.

Блок питания

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

Посему было принято решение вскрыть и заменить кондёры. После того как Иван аккуратно вскрыл блок (они оказывается запаянные), нам предстала безрадостная картина выгоревших дорожек и примерно трети оплавившихся деталей. Сильно повезло, что ноут выжил. Мы отпаяли провод от первого, отрезали штекер у второго и начали выяснять как из трёх проводов собирается нужное напряжение. Как и предполагалось: внутри сменных штекеров два провода соединялись с резистором и получалось нужное напряжение. Резистор был извлечен и мы соединили два провода. Теперь зарядка достаточной длины, чтобы ходить по комнате.

Солнечная батарея

Приехала мне спустя 40 дней китайская зарядка YG-020 выдающий по спеке 5.3В и 410мА. Тогда стояла солнечная погода, но подключенный телефон в авиа-режим продолжил разряжаться, может и не так медленно. Напряжение мы измерили, оно соответствовало заявленному, но вот силу тока (которая и была важна для заряки) померить было никак. А ковырять micro-usb кабель очень не хотелось. Дома у меня должен был где-то быть перебитый, который не жалко разрезать.

Кабель я не нашел, но нашел usb удлинитель от безымянной флешки, который мы и разрезали. Китайцы не пожалели пластмассы залив разъем, пока ковыряли пообрывали тонюсенькие провода. На этот раз припаять провода, а не только залудить, было доверено мне, что я и сделал.

6400 китайских люмен не хватает для зарядки телефона
Поскольку погода была пасмурная, Андрей светил на панель фонарём, а мы замеряли напряжение, но добиться больше 2мА не удалось, на окне за стеклом вообще выдавало 120мкА, что было на три порядка меньше необходимого для зарядки телефона. Андрей предложил ультрафиолетовую гипотезу о том, что не кварцевое окно может задерживать большую часть энергии. При открытом окне панель выдала 1.5мА, что больше чем в десять раз - таки да.

Итог: заряжаться если и можно, то только на открытом воздухе и в солнечную погоду, присоски для стекла бессмысленны, хоть и присасываются так, что не отодрать.

Про коллективное общение

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

2013-05-15

Концепция Пространства-Времени

Пространство и время два важнейших измерения: когда и где, позволяет точно найти себя, упорядочить события, понять как долго идти к определенной точке, сколько времени ждать - бесконечное количество ответов.

Во сколько лет человек осознает и начинает оперировать этими понятиями? Сами понятия можно узнать очень рано (в детском саду), но начать свободно оперировать ими - сильно позже, в школе. Можно даже нарисовать карту знаний как в цивилизации: числа, десятичная система счисления, арифметика, время, карта - сложно отсчитывать время и пройденное расстояние, если не можешь вычесть два числа в уме.

Интересно, насколько пониманию абстракций помогают реальные предметы. Например счетчик из магнитофона пониманию десятичной системы.

Сначала человек понимает числа в пределах десяти, потом сотни, потом понимает позиционный принцип заложенный в систему счисления. Cо временем граница переполнения для различных объектов растет: метры превращаются в километры, секунды в года. Но всё равно, у всех есть определенная граница, после которой наступает "много".

Этологический эксперимент

Летом, дядька собирается приехать с сыном в гости. Шестилетнему братану предстоит преодолеть больше тысячи километров в течении суток.

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

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

Итог: после вручения, атлас не вызвал большого интереса (надеюсь пока), а вот часы (уже радует) были освоены в течении одного дня. Посмотрим, чем всё закончится.

Интересное наблюдение

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

2013-05-07

Топологическая сортировка репозитория

Abstract

В систему контроля версий mercurial версии 2.6 [1] был добавлен новый алгоритм сортировки closesort в команду convert, позволяющий оптимизировать расположение коммитов, в которых закрываются ветки. В отличие от алгоритма datesort, который might well increase the size of the destination repo by 10-20 times [2], closesort незначительно меняет размер репозитория. Данный алгоритм может быть интересен для workflow в которых активно ведется работа с ветвями, причем все открытые ветви закрываются.

Rationale

Fig. 1 Визуальный мусор
При активной работе с ветками рано или поздно может возникнуть ситуация, когда необходимо массово закрыть устаревшие ветви. Множество очень старых ветвей приводит к тому, что граф заполняется визуальным мусором. На Fig. 1 изображен типичный пример такой массовой чистки устаревших ветвей, на 1 живую ветвь приходится 15 мусорных. 

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

Methods

Порядок версий необходимо менять, с использованием максимально стандартного механизма, желательно с использованием внутреннего API, что избавило бы от парсинга вывода команд.

Попытка 1

Поиск готовых или похожих решений натолкнул на обсуждение [3] проблемы оптимизации чрезвычайно больших репозиториев, вылившихся в итоге в расширение shrink-revlog [4]. Данное расширение как раз занималось топологической сортировкой и достаточно было написать собственную функцию сортировки к двум имеющимся. Алгоритм был написан, при этом потребовалось прокинуть внутрь функции сортировки объект репозитория.

Но первый же запуск на реальном репозитории привел к ошибке выхода за пределы массива. Выяснилось, что в репозитории используется два файла changelog и manifest [5]. В первом хранится информация о коммитах, а во втором информация о файлах [6], при этом, если в коммите не было изменений в файлах, то появится расхождение в нумерации между этими двумя файлами. Сортировка же changelog была запрещена, поскольку это повредит репозиторий.

Попытка 2

В качестве "Плана Б" можно было встроиться в стандартное расширение convert. В нем уже присутствовали branchsort, datesort и sourcesort. Необходимый алгоритм отличался от sourcesort одним условием:
        def makesourcesorter():
            """Source specific sort."""
            keyfn = lambda n: self.commitcache[n].sortkey
            def picknext(nodes):
                return sorted(nodes, key=keyfn)[0]
            return picknext

        def makeclosesorter():
            """Close order sort."""
            keyfn = lambda n: ('close' not in self.commitcache[n].extra,
                               self.commitcache[n].sortkey)
            def picknext(nodes):
                return sorted(nodes, key=keyfn)[0]
            return picknext 

И успешно решал поставленную задачу.

Pull request

Я сразу пошел в IRC разработчиков с целью обсудить данное решение, но особого интереса там не проявили и отправили в мейллист. После этого, Kevin предложил попробовать branchsort [7]. Данный алгоритм упорядочивал только самые простые случаи, но не справлялся со сложными. На IRC мне посоветовали засылать патч, раз никто не возразил. Патч был заслан и запушен Bryan [8]. В этот раз на всё-про-всё, от идеи до аппрува, ушел всего лишь месяц, а не пол года, как в прошлый раз [9].

Results

Максимальная ширина

На реальном рабочем репозитории с 5528 коммитов, максимальная ширина графа составляла 60 параллельных веток. После конвертации, ширина максимальная ширина репозитория уменьшилась до 26.

Средняя ширина

Подсчет средней ширины графа производился командой hg log -G | awk '/changeset/ {cnt++; width += (index($0,"changeset")-2)/2} END {print width / cnt}'. Данная подсчет не учитывает некоторых особых случаев, но подойдет для примерной оценки. До конвертации 21.16 и после 6.08.

Discussion

Алгоритм успешно, в разы сокращаяет ширину графа избавляя от визуального мусора. Из главных минусов можно указать то, что рассчет хэша у ревизии изменился между версиями 1.7 и 2.6, что приведет к несоответствию историй. Но, поскольку repository surgery можно проводить очень редко, это не является большой проблемой.

2013-05-04

Многомерное уважение

Вокруг декларируется максима: все одинаково имеют право на уважение. Само уважение воспринимается, как качественная характеристика. Я же не могу понять, как может человек, добившийся выдающихся результатов в какой-то области, рассчитывать на одинаковое уважение с бездельником, не добившемся ничего.

2013-05-02

Лови волну

Внезапный импульс

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

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

Challenge accepted

С этим тесно связаны вызовы, не банальное "на слабо", а те, которые можно бросить только самому себе. Когда до города 50 километров, а ноги уже не едут; когда пульс 180 и не хватает кислорода, а впереди бесконечные 50 секунд бега; когда руки не поднять и захлебываешься, а впереди еще пол километра. Можно отказаться в любой момент, остановиться и уйти, но говоришь себе еще пять секунд, еще пять метров, но они проходят и вроде бы есть еще силы на пять секунд, после которых уж точно нажму стоп, и еще, и еще.

If you can force your heart and nerve and sinew
To serve your turn long after they are gone,
And so hold on when there is nothing in you
Except the Will which says to them: "Hold on!"
R.K.