Castle

h1. Control Flow Graph Representation requirements

Набросок каталога требований к подсистеме библиотеки Castle, отвечающей за представление графов потока управления.

Каталог составлялся по мотивам CFG-представления, которое использовалось в инструменте Retrascope 0.1.3, и на данный момент является устаревшим. Тем не менее, некоторые требования каталога сохраняют свою актуальность.

# Граф потока управления — это ориентированный граф, состоящий из вершин Vertex, соответствующих операторам программы, и ребер, соответствующих зависимостям по управлению между ними. Библиотека для работы с графами потока управления состоит из двух частей — представления графов потока и методов работы с графами потока.

# Зависимости по управлению хранятся в виде перекрестных ссылок между родительскими и дочерними вершинами Vertex. Например, родительская вершина Vertex1 содержит ссылку на дочернюю вершину Vertex2 во множестве её дочерних вершин; дочерняя вершина Vertex2 содержит ссылку на родительскую вершину Vertex1 во множестве её родительских вершин.

# Вершины Vertex могут быть как содержащими внутренние вершины Node (композитными), так и атомарными. Композитные вершины имеют метод addVertex(Vertex v) добавления внутренней вершины.

# Вершина Vertex имеет следующие методы:

getType() - возвращает тип вершины;

getId() - возвращает уникальный строковый (String) идентификатор вершины;

getDescription(ExprTreePrinter printer) — возвращает строковое представление вершины в формате указанного принтера;

deepcopy() - возвращает копию вершины без копирования зависимостей по управлению;

hasParents() - возвращает false, если множество родительских вершин пусто, иначе true;

hasChildren() - возвращает false, если множество дочерних вершин пусто, иначе true;

getParents() - возвращает коллекцию родительских Vertex;

getChildren() - возвращает коллекцию дочерних Vertex;

getOnlyParent() - если вершина имеет единственную родительскую вершину, то возвращает её, иначе возвращает первый элемент коллекции родительских вершин;

getOnlyChild() - если вершина имеет единственную дочернюю вершину, то возвращает её, иначе возвращает первый элемент коллекции дочерних вершин;

addParent(Vertex v) — добавляет указанную вершину в коллекцию родительских, если указанная вершина не является родительской и добавление новой родительской вершины допустимо, иначе бросает исключение;

addChild(Vertex v) — добавляет указанную вершину в коллекцию дочерних, если указанная вершина не является дочерней и добавление новой дочерней вершины допустимо, иначе бросает исключение;

removeParent(Vertex v) — удаляет указанную вершину из коллекции родительских, если она там присутствует, иначе бросает исключение;

removeChild(Vertex v) — удаляет указанную вершину из коллекции дочерних, если она там присутствует, иначе бросает исключение.

#1 Вершина Vertex имеет ряд методов хранения и предоставления мета-информации. Мета-информация хранится в виде пар «<ключ, значение>». Ключ и значение мета-информации имеют строковый (String) тип. На ключи мета-информации накладывается требование уникальности.

hasMetaInfo(String key) — если хранилище мета-информации (далее - хранилище) содержит пару с указанным ключом, то возвращает true, иначе возвращает false;

getMetaInfo(String key) — если хранилище содержит пару с указанным ключом, то возвращает соответствующее значение, иначе возвращает null;

getMetaInfo() - возвращает всю доступную мета-информацию для данной вершины в виде Map<String,String>;

addMetaInfo(String key, String value) — если хранилище содержит пару с указанным ключом, то заменяет значение на указанное, иначе помещает в хранилище пару «<key, value>»;

removeMetaInfo(String key) — если хранилище содержит пару с указанным ключом, удаляет её, иначе не делает ничего.

# Некоторые вершины имеют методы получения используемых и определяемых в данной вершине переменных (зависимости по данным).

getUses() - возвращает множество Set<NodeVariable> переменных, используемых в данной вершине;

getDefines() - возвращает множество Set<NodeVariable> переменных, определяемых в данной вершине.

# Все вершины Vertex классифицируются по типам. Тип вершины определяет, сколько родительских и сколько дочерних вершин может иметь вершина, имеет ли она методы получения зависимостей по данным.

Тип вершины может принимать следующие значения: BasicBlock, Case, Merge, Sink, Source, Switch. В следующей таблице приведены сравнительные характеристики вершин указанных типов.

Вершина типа BasicBlock соответствует оператору базового блока. Базовый блок содержит упорядоченную последовательность присваиваний Assignment. Присваивание — это пара «<ranged_variable,expression>», состоящая из определяемой переменной (или части переменной) ranged_variable и используемого выражения expression. Выражение имеет тип Node. Определяемая переменная состоит из переменной NodeVariable и диапазона Ranged (возможно, пустого). Диапазон — это пара «<Node, Node>» индексов, определяющих некоторую часть определяемой переменной (элемент массива, часть битового вектора и т. п.).

Вершина типа Case соответствует значению условного оператора. Вершина содержит набор допустимых значений NodeValue оператора. Тип значений оператора должен совпадать с типом условного выражения в родительской вершине типа Switch.

Вершина типа Merge соответствует точке объединения потоков управления.

Вершина типа Sink соответствует точке завершения потоков управления.

Вершина типа Source соответствует точке начала потоков управления.

Вершина типа Switch соответствует условному оператору (оператору ветвления). Вершина содержит условное выражение типа Node. Тип выражения должен совпадать с типом допустимых значених всех дочерних вершин типа Case.

# Библиотека должна предоставлять реализации следующих методов работы с графами потока управления:

Метод приведения графа к форме однократных присваиваний (Single Static Assignment). Это означает, что каждый пусть в графе от точки начала до точки завершения для каждой определяемой в нем переменной должен содержать не более одного определяющего её присваивания.

Метод обратных постановок для указанной вершины типа Switch и указанной упорядоченной последовательности вершин типа BasicBlock. Это означает, что в обратном относительно указанного в последовательности порядке для каждой вершины типа BasicBlock выбираются определяемые переменные и в выражении вершины типа Switch заменяются все их вхождения на используемые в присваиваниях выражения.