Comments 10
В примере выше переменная
itдержит ссылку на некие данные, переменнаяit_nextссылается на внутреннюю ссылку вit, а при присваиванииit=it_nextвнутренняя ссылка переменнойitначинает указывать на внутреннюю ссылку вit_next, тем самым создав цикл в графе ссылок.
Прошу прощения, я чего-то не понял. Судя по формулировке, речь идет о каком-то односвязном списке:
struct T {
int data;
T *it_next;
} *it;Имея ссылку it на один из узлов, мы пишем:
T *it_next = it->it_next;
it = it_next;Вопрос: где тут циклы в графе ссылок? Максимум тут утечка памяти происходит, если на узел, ранее указуемый it, больше никто не ссылается. А циклов тут нет, есть только несколько равноправных ссылок на один участок памяти.
Еще в голову сейчас пришел такой вариант трактовки слов "ссылается на внутреннюю ссылку":
T** it_next = &(it->it_next);Но тогда присваивание it = it_next; невозможно (на С++, по крайней мере) из-за несоответствия типов.
В общем, нужны пояснения.
речь идет о каком-то односвязном списке
Нет, не верно. Тип Iterator это нечто вроде такого:
struct Iterator
{
T* data;
size_t size;
}
В статье речь идёт немного о другом - не о том, куда и как указывают какие ссылки/указатели во время выполнения, я о том, как во время компиляции это всё учитывается внутри компилятора. И одно не совсем совпадает с другим.
Давайте продемонстрирую сказанное диаграммой.
В начале функции граф ссылок выглядит как-то так:
Потом так:
А после присваивания it = it_next, так:
После присваивания it = it_next либо эти переменные начинают указывать на одну область памяти (если происходит просто запись указателя), либо в область памяти it копируется содержимое области it_next. Я не могу представить себе иной реализации оператора присваивания (в обычном его понимании). В любом случае,
третья диаграмма
не образуется никак:
Либо надпись "it" переезжает к "it_next" на правах соседа (а сама область остается безымянной).
Либо после перезаписи в области "it" ссылка должна измениться на указывающую на саму себя, что бессмысленно, но вполне реализуемо. Кроме того, область "some variable" при этом оказывается без ссылки и должна быть дропнута, а это уже явно получается выстрел в ногу. Не говоря уже о том, что у этих переменных должен быть разный тип:
T*иT**.
В статье речь идёт немного о другом - не о том, куда и как указывают какие ссылки/указатели во время выполнения, я о том, как во время компиляции это всё учитывается внутри компилятора. И одно не совсем совпадает с другим.
Быть может, у Вас граф ссылок хранит все связи, какие только были замечены, не только существующие единомоментно? Если так, то в таком графе легко можно нарисовать фигуру "все со всеми и во все стороны", операции обмена значений такое проделают с гарантией всего за несколько строк. И толку от такого графа не будет никакого.
Поясните, плиз, что такое "граф ссылок" и что он хранит.
Граф ссылок - слишком сложная абстракция для восприятия, да.
Если в кратце, то узлы этого графа - это переменные/ссылки, а рёбра - связи между ними. При этом связь эта родовая - а не указывающая, что означает, что один узел является производным от другого (порождён им). Иллюстрации в моём предыдущем комментарии как раз показывают подобные связи.
Быть может, у Вас граф ссылок хранит все связи, какие только были замечены, не только существующие единомоментно?
Граф ссылок таки хранит связи, которые логически были созданы. Если ссылка a указывает на переменную b, но не на c, то будет существовать только связь из a в b.
Граф ссылок -- абстракция вполне понятная и логичная. Но как и любая абстракция, она требует очень четкого определения, иначе, когда интуиция начинает давать сбои, она превращается в тыкву. А это происходит чаще, чем хочется, уж поверьте. Так что давайте определимся с терминами.
Первое. Что значит "переменные/ссылки"? Все переменные, когда-либо поименованные в программе? Должны ли быть ими не имеющие отдельного собственного имени элементы массива вроде a[2]? Или элементы массива с динамической адресацией a[i]? Или элементы структур a->next? Или очень косвенно адресуемые участки памяти a->next->next->arr[2]? Как насчет временных переменных, автоматически создаваемых компилятором в конструкциях вроде цепочек функций v.iter().next() (если такое есть в языке, конечно)?
Второе. Остается ли узел тем же самым, если его переменной что-либо присвоили? Или, согласно модели SSA, это означает фактическое создание новой переменной с назначением ей нового узла (и предварительной финализацией прежнего значения)?
Третье. Что значит "связь между переменными/ссылками"? То, что есть сейчас -- или то, что когда-то было или возможно будет? К примеру, в коде
struct T {
int data;
T *next;
};
T *a = new T; // 1
T *b = new T; // 2
a->next = b; // 3
//b = new T; // 4
//a->next->next = b; // 5
//b = a; // 6
//a = a->next; // 7между переменными a и b несомненно есть связь и она должна быть отражена в графе. Но что будет с графом, если начать поочередно снимать комментарии со строк 4-7?
Как мне кажется (это мое личное мнение), самая простая схема получается в модели SSA. Тем более, LLVM именно ее и использует. Проблема присваивания it = it_next при этом разрешается автоматически. Хотя остается проблема циклических ссылок вообще: a->next->next = a; -- но это уже совсем другая история.
Все переменные, когда-либо поименованные в программе
Все локальные переменные, ссылки, а также промежуточные переменные и ссылки.
Должны ли быть ими не имеющие отдельного собственного имени элементы массива
Единица контроля для переменных - одна стековая аллокация.
Остается ли узел тем же самым, если его переменной что-либо присвоили?
Узел остаётся тем же самым. Возможно только добавляются связи
что будет с графом, если начать поочередно снимать комментарии со строк 4-7
Пока что связи могут только добавляться. Связи удалятся вместе с окончанием жизни переменной.
a->next->next = a
А так вообще нельзя, пока что. Не позволено иметь более одного уровне косвенности на уровне типа - ссылка в структуре не может быть типа, который имеет ссылки внутри. Чисто технически это можно обойти через сырые указатели и создать библиотечный класс связанного списка, но при этом все элементы такого списка будут считаться частью переменной списка.
Возможно, что-то прояснить поможет документацитя. Но даже если прояснения не наступит, то это не страшно. На практике полного понимания внутреннего устройства компилятора не нужно, чтобы писать на языке что-либо.
Как произносится название Ü
Я все понимаю по поводу велосипедописания, это отличное времяпрепровождение, ещё и развивает прилично. (Сам этим занимаюсь, логгер очередной пишу)
Но с практической точки зрения, вот вы лет 5 уже на это потратили, а пользоваться этим вряд ли кто-то когда-то будет. Включая вас, если не считать разработку самого языка.
Как мне кажется, куда полезнее (и проще и быстрее) было бы написать линтер, который делал бы все те же проверки и запрещал бы ровно то же, что и ваш компилятор. При этом все коммьюнити, тулзы, утилиты, библиотеки остались бы от исходного языка.
Много людей могли взять ваш линтер на вооружение, и мир мог бы стать чуточку лучше.
Как пример, в го есть стандартный gofmt, а есть более строгий gofumt, и у него приличная аудитория.
Успехов в любом случае!
линтер, который делал бы все те же проверки и запрещал бы ровно то же
Это ограниченное решение. В некоторой степени доработка инструментария существующих языков может принести пользу. Но некоторые проблемы таким способом решить будет не возможно, ну или возможно, но очень сложно. Вон, статический анализатор C++ - PVS-Studio целая компания в течении многих лет разрабатывает и он всё ещё не идеален.
Но с практической точки зрения, вот вы лет 5 уже на это потратили, а пользоваться этим вряд ли кто-то когда-то будет.
Популяризация языка является не единственной целью его разработки. Да, это было бы желательно, но это не обязательно. Даже без этого я в процессе получил много опыта и (если можно так выразиться) развлекался этим.
Красава , держи планку высоко , и всегда старайся превзойти себя вчерашнего , сделать больше чем ты мог сделать когда либо .
Язык програмирования Ü — нелёгкий путь написания самодостаточного компилятора