Comments 72
Я думаю проблема утечек памяти такого рода может быть концептуально не решаемой технически, просто потому, что это не техническая ошибка, а ошибка проектирования.
Утечки памяти могут быть просто потому, что мы не правильно спроектировали ЖЦ определенных сущностей и они не высвободятся даже если не будут использованы никогда, просто потому, что система, их использующая, не может этого предсказать.
То есть вашим способом можно решить эту проблему на уровне структур данных, а она может быть на уровне модулей.
единственные, которые до сих пор не имеют нормального решения, это утечки памяти из-за циклических ссылок
Есть проблемы посложнее - гонки данных в многопоточной среде. Ваша идея их никак не решает, так что проверка заимствований никуда не денется. Более того - если до запрета рекурсивных ссылок мы могли сделать скажем lock free linked list, то после запрета у нас появится точка синхронизации - тот самый общий контейнер.
С другой стороны, для языка который на производительность не претендует идея интересная. Правда для такого языка и гц сгодился бы (и пользователю было бы проще), так что профит непонятен.
Ну и маленькая поправка - именно запрет рекурсивных ссылок не поможет, ведь можно сделать что А ссылается на B, B ссылается на С, а С ссылается на А. Так что компилятору придется строить дерево типов (кто на кого может сослаться).
Есть проблемы посложнее - гонки данных в многопоточной среде.
Это вообще не проблема, так как решается тривиальной синхронизацией.
Так что компилятору придется строить дерево типов (кто на кого может сослаться).
Не дерево, а обычный список ссылочных типов данных для проверяемого класса и рекурсивно для всех его родителей. Но это делается очень просто во время компиляции (правда в случае С++ придется извращаться из-за раздельной компиляции объектов трансляции, но это особенности сборки конкретного языка программирования, а не ограничения самой идеи).
Это вообще не проблема, так как решается тривиальной синхронизацией.
Что за тривиальная синхронизация? Целиком блокировать общий контейнер, пока поток работает с одним элементом?
Что за тривиальная синхронизация? Целиком блокировать общий контейнер, пока поток работает с одним элементом?
Я отвечал на замечание, про "Есть проблемы посложнее - гонки данных в многопоточной среде". Решение этой проблемы давно придумано - синхронизация доступа, но конкретные детали реализации зависят от требований.
Можно блокировать весь контейнер целиком, можно партицировать по частям, а можно синхронизировать доступ к каждому элементу по отдельности. Конкретное решение зависит от множества требований. Как нужно, так и делайте.
правда в случае С++ придется извращаться из-за раздельной компиляции объектов трансляции
а также любого языка поддерживающего раздельную\инкрементальную компиляцию. Ну т.е. да, это решаемо, в метаинформацию модуля надо будет добавить какие типы куда ссылаются или сделать отдельный неинкрементальный проход.
Это вообще не проблема, так как решается тривиальной синхронизацией.
если всё обвещать мьютексами то мнопоточность в ряде задач станет медленнее чем однопоточность. Поэтому это хорошее решение для языка где производительность не требуется (в питоне так вообще GIL, нет многопоточности нет и проблемы).
или сделать отдельный неинкрементальный проход.
Да, именно так, за счет двух проходов.
если всё обвещать мьютексами то мнопоточность в ряде задач станет медленнее чем однопоточность.
Согласен. Лучше вообще не использовать синхронизацию и обрабатывать только локальные данные, но все зависит от задачи и иногда без синхронизации доступа не обойтись.
но все зависит от задачи и иногда без синхронизации доступа не обойтись.
и вот все эти сложности с заимствованиями в Rust сделаны в том числе для того чтоб мы могли на этапе компиляции проверить - правильно ли сделана синхронизация. А ваша идея наоборот многопоточности мешает (добавляем обязательные контейнеры доступ к которым придется синхронизировать, хотя с рекурсивными ссылками могли бы сделать лок-фри).
Поэтому эта идея подходит только для языка где производительность не требуется.
Синхронизация доступа и утечки памяти из-за циклических ссылок вообще никак не связанные между собой проблемы.
Более того, строить граф выполнения для контроля синхронизации доступа, это очень плохая идея, так как некоторая информация бывает доступна только в рантайме и анализировать её статически невозможно.
Синхронизация доступа и утечки памяти из-за циклических ссылок вообще никак не связанные между собой проблемы.
Совершенно согласен. Именно поэтому в Расте столько внимания уделили первой, а на вторую вообще забили.
Просто конкретно ваше решение второй проблемы будет мешать строить лок-фри структуры данных для первой.
Более того, строить граф выполнения для контроля синхронизации доступа, это очень плохая идея, так как некоторая информация бывает доступна только в рантайме и анализировать её статически невозможно.
Согласен, графа выполнения тут недостаточно. Я сразу сказал что эта проблема посложнее циклических ссылок.
Согласен, графа выполнения тут недостаточно. Я сразу сказал что эта проблема посложнее циклических ссылок.
Я немного не это имел ввиду. Конечно, обе проблемы сложные, но я писал про то, что проблема синхронизации доступа все же решается за счет использования различных элементов межпотоковой синхронизации (т.е. имеет решение для рантайма), тогда как полного решения для проверки циклических ссылок не существует ни в рантайме ни статически.
У проблемы циклических ссылок есть два общеизвестных решения - одно уязвимо к ошибкам программиста (следить за ними вручную), другое несет расходы в рантайме (гц). Для синхрнизации эти решения тоже есть - соответственно синхронизировать вручную (уязвимо к ошибкам программиста) и запретить одновременный доступ к данным (несет расходы в рантайме).
А почему нельзя решить это подсчетом ссылок при выходе из области видимости или при записи в ссылочное поле?
B func() {
var a = new A(); // refCntNewA = 1
var b = new B(); // refCntNewB = 1
b->field = a; // refCntNewA++ (2)
a->field = b; // refCntNewB++ (2)
// refCntNewA--; get ref for a->field; refCntNewB-- (1, 1)
return b; // refCntNewB++; refCntNewB-- (1)
}
var b = func(); // refCntNewB++; refCntNewB-- (1)
b->field = null; // refCntNewA-- (0, free memory newA)
То есть это тоже расходы в рантайме, но это не совсем gc. Количество ссылочных полей в классе известно при компиляции, компилятор может подготовить нужные инструкции.
Всё в компайл-тайме и не проверишь, количество ссылок может зависеть от входных данных в рантайме.
А почему нельзя решить это подсчетом ссылок при выходе из области видимости или при записи в ссылочное поле?
Потому что динамические объекты могут иметь циклически ссылки друг на друга. Для них нет "области видимости" как у автоматических переменных, ведь они создаются вручную и удаляются, когда счетчик ссылок доходит до нуля. Но этого никогда не произойдет, если ссылкой владеет такой же динамический объект.
количество ссылок может зависеть от входных данных в рантайме.
Из-за этого невозможно проанализировать зависимости и переход владения статическим анализатором.
Я же привел пример с динамическими объектами. Ссылка на динамический объект хранится в локальной переменной, у которой есть область видимости.
Вы привели пример в котором удаление объектов происходит только после разрыва циклической ссылки вручную
b->field = null; // refCntNewA-- (0, free memory newA)
А ссылка на динамический объект в локальной переменной, у которой есть область видимости в строке
var b = func(); // refCntNewB++; refCntNewB-- (1)
не влияет на удаление зацикленных объектов, так как удаление локальной переменой var b не обнуляет счетчик ссылок, так как последняя ссылка все еще находится тут: a->field = b;
происходит только после разрыва циклической ссылки вручную
Не после разрыва циклической ссылки, а после достижения нулевого количества ссылок на область памяти.
Можно не возвращать b из func, тогда для нее будет такая же обработка, как для a, и память освободится для обоих, без записи null в поле.
// refCntNewB--; get ref for b->field; refCntNewA-- (0, 0)
удаление локальной переменой var b не обнуляет счетчик ссылок, так как последняя ссылка все еще находится тут
Удаление локальной переменной, которая в func, не обнуляет счетчик ссылок, потому что b возвращается как результат. Ссылка, которая в b, записывается во временную переменную для возврата, счетчик refCntNewB увеличивается, локальная переменная b удаляется, refCntNewB уменьшается. Поэтому там указаны одновременно "++" и "--".
А почему нельзя решить это подсчетом ссылок при выходе из области видимости или при записи в ссылочное поле?
В принципе, идея рабочая. Но с большими накладными расходами в рантайме.
Как только мы обнуляем любую сильную ссылку (или перед присвоением ей другого значения), нужно рекурсивно обойти структуру, на которую она указывала (ни по какой ссылке нельзя проходить дважды), и для каждого узла сравнить его refcnt с количеством [пройденных] ссылок, указывающих на этот узел. Так можно понять, есть ли ссылки снаружи, и если нет - удалить всю структуру.
Не совсем рекурсивно. Проходим по всем ссылочным полям, уменьшаем refCnt. Если стало 0, удаляем. При удалении проходим по всем ссылочным полям, делаем то же самое. Обработка последовательная, можно обойтись циклом и даже без стека, нужен просто массив для добавления всех ссылочных полей текущего объекта. Дважды по ссылкам на одну область памяти как раз нужно проходить, так как refCnt соответствует их количеству, поэтому отслеживать это не надо. Сравнивать 2 количества не нужно, только refCnt с 0.
Это как бы garbadge collector, только распределенный по времени, каждый раз по чуть-чуть. Мне кажется, так задержки будут небольшие и более предсказуемые. Можно конечно представить linked list на миллион элементов, у которого мы удаляем первый, и остальные удаляются по цепочке, тут задержка будет выше среднего, но их и с явным управлением памятью нужно удалять.
UPD: Хм, наверно все-таки в массиве будут поля не только текущего объекта, но это будет просто вектор, куда поля для обработки добавляются в конец.
Сравнивать 2 количества не нужно, только refCnt с 0
Это классический подсчёт ссылок. Он не справляется с циклами.
Я же привел пример цикла, там 2 объекта ссылаются друг на друга. Ссылки подсчитываются каждый раз при записи в любую ссылочную переменную. Удаление стековых переменных эквивалентно записи null в них.
Проходим по всем ссылочным полям, уменьшаем refCnt. Если стало 0, удаляем
При потере ссылки на объект уменьшаем его refCnt.
А что предлагаете делать со ссылками внутри объекта, я не понял. То ли проходить по ним и уменьшать refCnt целей, если в самом объекте refCnt стало 0, то ли всегда при потере ссылки.
Если на эту область памяти больше никто не ссылается, мы ее освобождаем. Это эквивалентно предварительной записи null во все ссылочные поля этого объекта. То есть у всех ссылочных полей уменьшится refCnt для их областей памяти, и дальше работает та же логика. Если refCnt уменьшился, но не 0, то с полями ничего не делаем, они же указывают на другие области памяти, для них количество ссылок не изменилось.
Немного не понял про рантайм, все современные GC спокойно работают с цикл. ссылками и чистят память правильно.
если всё обвещать мьютексами то мнопоточность в ряде задач станет медленнее чем однопоточность.
так речь шла за гонку, а не за производительность. Так или иначе возникает необходимость некоторой синхронизации - либо лок мьютексом, либо какой-нибудь CAS.
если всё обвещать мьютексами то мнопоточность в ряде задач станет медленнее чем однопоточность.
Скорость - не самая большая проблема при избытке синхронизации. Ибо при некоторой сноровке (думаю, квалификации джуна для этого достаточно) из двух mutex несложно сделать один deadlock ;-)
а также любого языка поддерживающего раздельную\инкрементальную компиляцию. Ну т.е. да, это решаемо, в метаинформацию модуля надо будет добавить какие типы куда ссылаются или сделать отдельный неинкрементальный проход.
Эх, если бы был какой-то поддерживающий local reasoning, но композабельный подход проверять, что разные объекты в вашем языке совместимы друг с другом… что-то там со словом «типы», возможно.
Короче, всё уже придумано до нас: https://www.arxiv.org/pdf/2503.07328 . Совместимость этого фреймворка с линейными типами позволяет статически гарантировать, что определённый ресурс освобождён, даже если там внутри есть циклические ссылки.
Apple, к примеру, сознательно отказался от gc. И ничего, не жужжат...
Так в Rust один из способов обойтись без self-referential структур - это и есть устроить хранилище данных в векторе, а в структурах вместо ссылок хранить индекс на элемент. Но это опять же влечет лишние накладные расходы:
вместо прямого доступа по ссылке - двойной прыжок по памяти,
лишнее хранилище,
если в коде используется несколько таких хранилищ, то возникает проблема изоляции индексов по типу, благо уже крейты для этого, но про это надо помнить,
громоздкая логика по аллокации, удалению элементов, дефрагментации пространства для долгоживущих коллекций - по сути нужно переизобретать garbage collector
Но это решение (как и предложенное в статье) все равно не решает проблему статического анализа циклических ссылок: оно заметает проблему под ковер путем изоляции такой коллекции внутрь другой коллекции.
все равно не решает проблему статического анализа циклических ссылок: оно заметает проблему под ковер путем изоляции такой коллекции внутрь другой коллекции.
Еще как решает. Сравнение ссылок на конкретные объекты, которые есть только в runtime и анализ графа выполнения заменяется на обычный статический анализатор, который работает на этапе компиляции.
В ряде задач проблему циклических ссылок можно решить через использование кастомного аллокатора памяти типа Arena. Просто и эффективно.
Правда не универсальное решение, но где подходит - это пушка. И нет утечек, и скорость выделения/освобождения памяти максимальнр быстрая.
Тут, как я понял, предлагается то же самое, только не на уровне аллокатора, а на прикладном уровне: вместо аллокатора заводится контейнер с сильными ссылками, а внутри прикладной структуры держатся только слабые ссылки или индексы. Правда вместо выигрыша по производительности получается проседание ;)
вот и скорость и циклы memory-leak , задача не тривиальная, и что интересно компилируется и выполняется
Кстати говоря. Допустим мы запретили циклические сильные ссылки и теперь половина ссылок - слабые. Как для них предполагается решать проблему use-after-free?
В тайтле эррор: Не "избавится", а "избавитца".
Я думаю проблема утечек памяти такого рода может быть концептуально не решаемой технически, просто потому, что это не техническая ошибка, а ошибка проектирования.
Утечки памяти могут быть просто потому, что мы не правильно спроектировали ЖЦ определенных сущностей и они не высвободятся даже если не будут использованы никогда, просто потому, что система, их использующая, не может этого предсказать.
То есть вашим способом можно решить эту проблему на уровне структур данных, а она может быть на уровне модулей.
Спасибо за комментарий, я его даже закрепил под публикацией. Вы просто и кратко описали цель моего предложения.
Не уверен, что правильно понял насчет модулей, мне кажется, что модули - это тоже же самые структуры данных, которые также могут контролировать на предмет описанных в статье ограничений.
Я имею в виду модули приложения, на уровне архитектуры.
Например, есть у вас список товаров и другие компоненты их используют - достают из БД или из сети при необходимости, как то обрабатывают, сохраняют при изменении.
Кешированный список хранится в некотором динамическом массиве.
Так как в будущем они могут понадобится, вы их храните формально бессрочно, у них есть владелец, с точки зрения приложения проблем нет.
Для того, чтобы их высвободить, нужно создать некую логику, которая, к примеру, помечает элементы как "очень долго не используемые" по метке времени.
Если эта логика неправильна или не реализована - товар не высвободится никогда.
Перечитайте внимательно первый абзац - там у вас пару опечаток (ссылка дважды, буквы кое где потеряны).
Указано что сборщик мусора решает другие проблемы но не циклические ссылки - но вот как раз сборщик мусора (как в java например) - решает проблему циклических ссылок любой сложности - ведь оперирует графом от рутов, а если никто из рутов косвенно не ссылкается на объекты, то они могут сколько угодно держать сильные ссылки на себя и друг друга но будут собраны.
Не до конца понял идею - но кажется вы предлагаете запретить объектам держать сильные ссылки на самих себя (свой тип) и заодно проверять каждую пару объектов на то, что они не могут держать сильные ссылки друг на друга одновременно (если T держит ссылку на любой объект C, то C не скомпилируется если держит ссылку на любой T) и так же проверять тройные и далее связи t -> c -> q -> t например.
В таком случае мало какие коллекции вы сможете использовать. Предложенное решение для связного списка с контейнером в котором хранятся сильные ссылки - требует хранить их в какой то структуре, а значит это будет массив - и связный список вырадится до массива. И если потерю списков ещё можно пережить, то вот с потерей деревьев все будет куда тяжелее, а они тоже станут массивами со всеми вытекающими o(n) вместо o(log(n))
Следующим ударом станет то, что объект содержащий массив не сможет стать элементом массива сам (хотя я не уверен как в rust с generic - может если нет универсальных типов то можно привязаться к конкретным, тогда все не так страшно).
И странно все становится с интерфейсами и делегированием - объект T реализующий интерфейс Z не может хранить делегата типа Z, которому передать управление полностью или частично. А значит часть паттернов проектирования типо композиции отваливается.
Нужно ещё посмотреть в сторону инструментов которые неявно работают со ссылками типо наследования (особенно множественного для интерфейсов), лямбд, делегатов - наверняка что-то ещё отвалится.
требует хранить их в какой то структуре, а значит это будет массив - и связный список вырадится до массива.
Вырождения не случится. Связные списки остаются, просто меняется их безопасная реализация в которую добавляется новая сущность - массив для хранения элементов списка, так как ссылки между узлами разрешаются только слабые, но все важные свойства списка остаются в силе.
Следующим ударом станет то, что объект содержащий массив не сможет стать элементом массива сам
Это возможно только в одном случае, кода элементом массива должен быть сам массив. Что-то вроде этого: std::vector<std::vector<std::vector<std::vector<std::vector .... >>>> и т.д. правда у меня не получилось записать такую рекурсию даже без предлагаемых ограничений :-)
И странно все становится с интерфейсами и делегированием - объект T реализующий интерфейс Z не может хранить делегата типа Z, которому передать управление полностью или частично.
Не вижу никаких проблем. Интерфейс ничего не говорит про реализацию (на то он и интерфейс), и в нем вы можете сделать связь на делегат этого же типа, только не за счет владеющей ссылкой, с помощью слабой. А для хранения точно так же как и в случае списков, используется отдельный контейнер для хранения сильных ссылок, но это уже детали реализации, которые в интерфейсе указывать не требуется.
Связные списки остаются, просто меняется их безопасная реализация в которую добавляется новая сущность - массив для хранения элементов списка
А кроме того каждый узел должен хранить свой индекс в этом массиве и обновлять его если индекс изменился при удалении другого элемента.
И еще ньюанс, правда со списками он не очень заметен, проще на примере дерева рассмотреть. Как удалить узел в дереве с сильными ссылками? Обнуляем в родительском узле ссылку на этот узел. Остальное за нас сделает RAII. Как удалить узел в дереве со слабыми ссылками? Рекурсивно проходим по всем потомкам удаляя их из массива (и при каждом удалении обновляем индексы затронутых узлов. За счет трюка с переносом последнего при каждом удалении будет обновляться всего один индекс, но все же). А если вдруг забыли удалить узел (допустим, у нас сложная схема балансировки дерева), то он и его потомки так и останутся висеть в массиве, создавая неявную утечку памяти (формально утечки вроде и нет, но если дерево висит в памяти пока работает программа, то узлы так и будут занимать память).
Я не исследовал возможные оптимизации при реализации списков или деревьев (у которого в каждом листе есть список). Поэтому не могу аргументированно ответить на ваши возражения. Конечно дополнительные накладные расходы обязательно будут, но это неизбежная плата за гарантированную безопасность.
Тем более у вас всегда остается возможность сделать не безопасную реализацию списка или дерева. Просто в этом случае вы сознательно идете на некоторый рассчитанный риск в одном конкретном случае, тогда как в настоящий момент вы рискуете всегда.
это первая часть моего комментария про накладные расходы. А вторая (начиная с "ньюанс") - про то мы жертвуем как раз безопасностью. Сейчас нам надо вручную проверять не появилось ли циклических ссылок, а со слабыми ссылками надо будет проверять не забыли ли мы освободить память (удалив элемент из дерева но оставив в массиве).
мы жертвуем как раз безопасностью
Мы не жертвуем безопасностью, а наоборот её обеспечиваем, так как у нас все сильные ссылки всегда находятся в одном месте, а не раскиданы по каждому элементу дерева или списка.
Как удалить узел в дереве со слабыми ссылками?
Я вам уже ответил, что не анализировал возможные реализации, но самый очевидный способ - при удалении объекта, удалить так же и те объекты, на которые указывают слабые ссылки. После этого RAII сделает все автоматически. Кроме этого, в качестве контейнера для хранения сильных ссылок, лучше всего брать не массив с доступом по индексу, а какой нибудь deque, чтобы не протухали итераторы при удалении элементов контейнера. Или в случае использования массива, не удалять сами элементы, а только освобождать выделенную под узел память не изменяя размер самого контейнера.
так как у нас все сильные ссылки всегда находятся в одном месте
но при этом они никак не связаны с основной структурой данных. Фактически мы защитились от кольцевых ссылок ценой отказа от автоматического управления памяти и теперь сами должны следить за тем чтоб все вовремя удалялось.
самый очевидный способ - при удалении объекта, удалить так же и те объекты, на которые указывают слабые ссылки.
способы можно придумать разные, в конце концов живут же в Си без всякого автоматического удаления. Но это на мой взгляд это слегка противоречит исходной задаче.
ценой отказа от автоматического управления памяти и теперь сами должны следить за тем чтоб все вовремя удалялось.
Да с чего вы это взяли? Автоматическое управление памятью c RAII никуда не делось и принципы работы со списком и деревом никак не меняются. Меняется реализация в которой входом (головой списка) становится не сильная, а слабая ссылка.
Реализация с сильными ссылками: удаляем ссылку на узел, он и его потомки автоматически удалятся если на них больше нет сильных ссылок. От автора структуры данных не требуется ничего кроме ручной проверки того что нет циклических сильных ссылок (если это дерево а не граф, то собственно и доказывать нечего).
Реализация со слабыми ссылками: автору структуры данных нужно сделать deque хранящий все узлы, хранить итераторы в узлах, реализовать удаление всех потомков при удалении узла (если я правильно понял вашу идею), нигде не ошибиться а лучше покрыть тестами то что при удалении узла он удалится также и из массива, и в итоге все равно в каком-нибудь редком случае словить баг (например если где-то еще осталась сильная ссылка на узел а потом она удалилась).
По-моему второй вариант не слишком отличается от ручного управления памятью.
Выше я вам уже отвечал, что не анализировал возможные реализации, а просто рассуждать на пальцах словах - так себе идея.
Нужно будет попробовать реализовать список и дерево в данной парадигме, тогда можно будет хотя быть по коду проанализировать. Хотя иногда даже при наличии кода мнения расходятся.
Про связные списки - вспоминаем что для них характерны операции вставки (а это значит что массив в отдельном блоке придётся перевыделять чтобы расширить длинну как это делает вектор) и удаления - а это значит что будет накапливаться пустые элементы, и массив надо будет шринкать периодически переиндексируя элементы, и учитывая это - мы и получаем связный список с проблемами вектора (например необходимостью аллоцировать большие блоки непрерывной памяти). Ну и с деревьями все еще хуже.
Про массивы - не понял почему вы рассматриваете только ситуацию прямо хранения вектора в векторе. Если вектор хранит T а T хранит любой другой вектор - это возможность циклической ссылки (T ссылается на веткор в котором хранится), а значит любой подкласс не может хранить вектор, если в векторе хранится любой из родителей. Vector -> Q -> V -> T -> Vector - тоже может быть циклической ссылкой. Опять же, я не знаком с типизацией в rust и если можно гарантировать на этапе компиляции что вектор хранит элементы строгого типа, то проблема получается только с векторами одинаковых типов, но многие языки такого не гарантируют.
С интерфейсами как будто ещё страшнее - если класс A реализует интефесы I, J, L, то ни какой из классов лежащих в нём по иерархии не имеет право хранить сильную ссылку ни на один из этих интерфесов, ведь A:I -> Q -> J -> Z -> I - циклическая ссылка если в Z в качестве I записан A:I.
А если у нас два класс A:I и B:J при этом B -> I и A -> J - как тут определить циклическую ссылку на этапе компиляции? Получается мы вообще скорее всего интейфесы хранить не можем в полях класса
Про композицию - та-же проблема что и с деревьями - нам нужно хранить все в отдельной плоской структуре - и логику и ссылки - а знать паттерн рассыпается просто.
Про связные списки - вспоминаем ...
Выше я отвечал, что пока не анализировал возможные реализации, а рассуждать на словах не хочется. Как сделаю список и дерево в данной парадигме, тогда можно будет хотя быть код обсудить.
Про массивы - не понял ...
Приведите пример кода хотя бы на С++, про который вы говорите. Как я уже написал, у меня не получается представить такую рекурсивное определение без создания отдельного класса контейнера для элемента массива. Но именно такой тип элемента и будет выявляться анализатором как рекурсивная ссылка.
Тоже сами и про интерфейсы. Лучше бы конкретный пример.
Про циклические интерфейсы (в с++ это асбтрактные классы с виртуальными методами)
class T {
public: virtual ~T() = default;
};
class Q {
public: virtual ~Q() = default;
};
class A : public T {
public: Q* field;
};
class B : public Q {
public: T* field;
};это простой пример в нотации которой я записывал выше A: T, B: Q, A -> Q и B -> T
Т.к. в field A может быть записан любой Q, то это может быть и B, в поле filed которого может быть записан любой T - а это может быть и A. Циклическая ссылка.
При этом надо сразу учесть что его можно сколь угодно усложнять на вложенность
// добавим класс R хранящий Q
class R {
public: virtual ~Q() = default;
};
// изменим класс A
class A : public T {
public: R* field;
};
// B оставим как есть.
// Теперь молучаем ситуацию, что A может хранить R которы хранит ссылку
// на B (приведённый к Q) который хранит ссылку на A (приведённый к T)
// Усугублять можно любым уровнем вложенности Проблема этого в том, что фактически реализовав библиотечный интерфейс например, а потом использовав внутри библиотечный класс - можно получить такой цикл где-то внутри библиотеки, за пределами своего кода, и даже понять на каком этапе не собирается - будет нетривиально. А на большом проекте где много сущностей и связей со сторонними блоками кода требующими принимать реализации интерфейсов или делегаты - будет еще больнее.
Про массивы перечитал спецификацию С++, там проблема будет только при использовании void* в расте аналогично dyn Any - которые позволяют хранить в generic любой тип. Ну т.е. получается dyn и аналоги придётся запретить вообще
class T {
public:
std::vector<void*> items;
};
class Z {
public:
std::vector<void*> items;
};Большое спасибо за подробное описание. Теперь понятно о чем идет речь и наверно уже получится прояснить некоторые детали реализации.
Описанная вами проблема с интерфейсами, это очень интересная комбинация двух случаев, которые можно назвать как ссылка через наследника (когда возникает циклическая ссылка через родительский класс) и "взаимная или кросс ссылка" (когда два класса не являются родственными, но имеют ссылки на друг на друга или через третьи классы).
Причем последний тип "взаимных ссылок", например в С++, может усугубляться еще и тем, что в С++ ссылочные типы можно использовать с предварительным объявлением, тогда как само определение типа может находиться в другой единице трансляции и быть не доступным статическому анализатору на момент обработки исходного файла программы.
Данные проблемы мне известны, но они не являются нерешаемыми. Просто в общем случае их нельзя разрешить за один проход анализатора.
Но данная проблема успешно решается за два прохода (по крайне мере для С++). Первый проход - только анализ синтаксиса и создание базы используемых классов с их наследниками, которые имеют поля ссылочных типов данных. На втором проходе анализатор уже будет иметь полную информацию обо всех типах данных, которые используются в приложении. (как раз сейчас добавляю прототип анализатора для С++ в библиотеку и как он будет готов, напишу).
Второй случай с void* в С++ и dyn Any Rust не менее интересный, но по другой причине. Ссылка void * (произвольный указатель) не является ссылкой на конкретный тип (т.е. её можно кастовать к любому произвольному типу), поэтому для анализатора она должна быть под запретом как не безопасная.
А вот пример с произвольным типом в Rust (точнее не только в нем, а вообще в любых языках программирования), относится не к языку, а к системе указания типов, которая не может покрыть все возможные сценарии использования. В системах типов, в известных мне языках программирования, не существует лексической конструкции, которая бы запрещала использование отдельных типов данных.
Так уж повелось (из-за повторения модели наследования классов ООП), что типы в языках указываются через перечисление и их принято только расширять, но в данном случае в Rust (ну или в другом языке) не хватает лексической конструкции, которая бы сужала список разрешенных типов, потому что типы данных, это не объекты ООП!
Тогда в случае гипотетического примере для Rust fn func<T: Any except Z>(value: &T) - т.е. любой тип данных, кроме Z. Структуру данных написать не могу, но надеюсь, что смысл понятен. В этом случае проблема с Any generic в Rust полностью снимается, так как становиться возможным анализировать типы данных статически в полном объеме.
Почему не сделать так:
Для двусвязного списка ссылки вперед сильные, ссылки назад слабые -- циклов по сильным нет
Для бинарного дерева поиска ссылки на потомков сильные, на предков (ели нужны) слабые -- тоже циклов нет
В произвольной графовой структуре делаем что-то такое: делаем специальный указатель, который а) сильный если номинально указывает на область памяти с бОльшим номером, чем адрес объекта, где он используется; б) слабый в обратном случае
Первые два я на практике несколько раз использовал. 3ий придумал пока читал статью и честно говоря сомневаюсь, что до меня никто такого не предлагал. Сходу у 3 вижу несколько потенциальных проблем, но они кажутся решаемыми.
это мы знаем что у нас дерево/список/граф, а компилятор это проверить не может. В статье предлагается совсем запретить сильные ссылки из типа Т на тип Т - это компилятор проверить может, но ваши 3 варианта тогда он тоже запретит.
Насчет третьего варианта - если у нас граф не фиксированный а изменяется, то рано или поздно возникнет момент когда на узел ссылаются только узлы с большим адресом и соответственно он удалится.
Насчет третьего варианта - если у нас граф не фиксированный а изменяется, то рано или поздно возникнет момент когда на узел ссылаются только узлы с большим адресом и соответственно он удалится.
Так да, Вы в точности объяснили суть этой схемы, уточню что если на граф из объектов нет внешних сильных ссылок, то в нем в каждый момент времени будет узел, на который есть только слабые ссылки
тогда я не понимаю в чем отличие от графа где все ссылки будут слабыми. И там и там придется отдельно держать контейнер с сильными ссылками на каждый узел, если мы не хотим чтоб какой-то узел случайно удалился.
Немного подумал, попробую вот так расписать. Пусть у нас есть unique_ptr и shared_ptr -- стандартные для C++ сильные указатели. Докидываем к ним mixed_ptr, работающий по 3 варианту моего описания. Если развивать идею автора с запретом ссылок можно договориться, что для shared и unique они запрещены, а для mixed нет. Но я скорее думал в направлении, что на стеке все ссылки shared/unique, а в heap -- mixed.
Да, в этом случае классический связной список сделать не получится. Для связного списка в новой парадигме потребуется отдельный контейнер для хранения элементов списка с использованием сильных ссылок, так как самим элементам списка будет запрещено иметь сильные ссылки на свой собственный тип
Но так мы уходим от языка общего назначения. То есть, запрещаем программисту самостоятельно создавать списки/деревья (а вдруг он накосячит) и заставляем его пользоваться списками/деревьями, которые предоставляет стандартная библиотека (написанная, в термина раста, с unsafe), которые точно проверены.
Нет, не запрещаем, но сообщаем, что классическая реализация связного списка не безопасная.
Как уже писал, связной список можно сделать и с использованием слабых ссылок, но для хранения сильных ссылок потребуется отдельный контейнер.
Например как нибудь вот так
template <typename T>
struct LinkedWeakNode {
typedef std::weak_ptr<LinkedWeakNode<T>> WeakType;
WeakType next;
T data;
LinkedWeakNode(const T & value) : data(value) {
}
};
template <typename T>
class LinkedWeakList {
public:
typedef LinkedWeakNode<T> NodeType;
typedef std::shared_ptr<NodeType> SharedType;
SharedType m_head;
std::set<SharedType> m_data;
LinkedWeakList() : m_head(nullptr) {
}
void push_front(T && data) {
SharedType node = std::make_shared<NodeType>(data);
m_data.insert(node);
node->next = m_head;
m_head = node;
}
void push_back(T && data) {
SharedType node = std::make_shared<NodeType>(data);
m_data.insert(node);
if (!m_head) {
m_head = node;
return;
}
SharedType temp = m_head;
while (temp->next.lock()) {
temp = temp->next.lock();
}
temp->next = node;
}
void pop_front() {
if (!m_head) {
std::cerr << "List is empty." << std::endl;
return;
}
SharedType temp = m_head;
m_head = m_head->next.lock();
m_data.erase(temp);
}
void pop_back() {
if (!m_head) {
std::cerr << "List is empty." << std::endl;
return;
}
SharedType temp = m_head->next.lock();
if (!temp) {
m_data.erase(m_head);
m_head.reset();
return;
}
while (temp->next.lock()->next.lock()) {
temp = temp->next.lock();
}
m_data.erase(temp->next.lock());
}
std::string to_string() {
if (!m_head) {
return "nullptr";
}
std::string result;
SharedType temp = m_head;
while (temp) {
result += std::to_string(temp->data);
result += " -> ";
temp = temp->next.lock();
}
return result;
}
};
Как говорится, "нафига козе баян"?
Если у нас есть вектор, зачем ещё нужен WeakPtr?
У списка есть конкретные преимущества, которые ваш подход полностью уничтожает: удаление элемента под указателем и вставка после указателя за O(1).
Все свойства списка сохранились и причем тут вектор?
А, вижу тут не вектор.
std::set<SharedType> m_data;
Кстати под капотом у set сбалансированное дерево, с оценкой операций log(N), а не O(1). Которое тоже, либо "unsafe", либо потребует хранилища сильных ссылок на ноды ))
Если LinkedWeakList написан прикладным программистом, а не является частью стандартной библиотеки, никто не мешает "забыть" m_data.erase, вот и утечка памяти. То есть, держать в голове надо гораздо больше (у вас больше кода), чем при классическом связном списке.
Согласен, что кода больше, но этот код гарантирует отсутствие циклических ссылок в автоматическом режиме, тогда как для классической реализации все действительно нужно держать в голове.
Отсутствие циклических ссылок не самоцель, нужно отсутствие утечек.
И получается, что пишем замудрённый код, и всё равно можем посадить утечки.
Ничем не отличается от того, как если бы вручную спроектировать правильно. Только миллионы гемороя и ненужных приседаний с конвертацией слабой ссылки в сильную с корректной обработкой ошибок. Вместо use(a->b->c)
if (auto bref = a->b.lock()) { if (auto cref = bref->c.lock()) { use(cref.ptr()); } else { // а я не придумал что тут делать, по идее такого быть не должно
Это же всё не ограничивается стандартыми контейнерами. Например, если я пишу GUI-библиотеку, то не смогу ограничиться лишь вектором дочерних контролов внутри контрола, придётся где-то сбоку присобачивать глобальное хранилище сильных ссылок на компоненты и не забывать добавлять туда/удалять оттуда. А если я ошибочно удалил из глобального сета, но слабые ссылки остались где-то в дереве, то что тогда? gc решает эти проблемы лучше.
Можно ли навсегда избавиться от утечек памяти из-за циклических ссылок?