История вопроса:
В Rust 1.26 язык представил impl Trait в позиции возврата (RPIT), чтобы позволить разработчикам скрывать сложные конкретные типы — такие как вложенные адаптеры итераторов или структуры, созданные замыканиями — при этом сохраняя преимущества производительности статической диспетчеризации через мономорфизацию. Эта функция создаёт непрозрачный экзистенциальный тип, который компилятор разрешает в единую конкретную реализацию во время компиляции, предотвращая утечку деталей реализации через границы API. В отличие от обобщений, которые выбираются вызывающим, RPIT выбирается реализацией функции, но всё же требует, чтобы компилятор знал точный размер и размещение конкретного типа для генерации правильного машинного кода.
Проблема:
Когда функция пытается вызывать саму себя рекурсивно, возвращая impl Trait, конкретный возвращаемый тип логически должен содержать себя, создавая само-ссылающуюся определение типа бесконечного размера. Rust строго требует, чтобы все возвращаемые значения, помещенные в стек, реализовывали трейты Sized, что обязывает компилятор заранее вычислить фиксированное размещение памяти и выравнивание во время компиляции. Поскольку рекурсивный возврат impl Trait подразумевает неограниченное расширение типа, при котором каждый кадр вызова вкладывает предыдущий, компилятор не может определить размер хранения или смещения кадра стека, что приводит к ошибке обнаружения цикла во время проверки типов.
Решение:
Решение требует явного разрыва рекурсивного цикла путем введения индирекции через распределение в кучу, что преобразует бесконечно-размерную рекурсивную структуру в указатель фиксированного размера. Возвращая Box<dyn Trait>, функция вместо этого возвращает «толстый» указатель, содержащий указатель vtable и указатель данных, оба из которых являются Sized, независимо от глубины рекурсии. В качестве альтернативы можно определить рекурсивный enum, где варианты явно оборачивают себя в Box или другие типы указателей, четко указывая, что рекурсивные данные находятся в куче, а тип возвращаемого значения остается конкретной, Sized структурой.
trait Expr { fn val(&self) -> i32; } struct Literal(i32); impl Expr for Literal { fn val(&self) -> i32 { self.0 } } struct Sum(Box<dyn Expr>, Box<dyn Expr>); impl Expr for Sum { fn val(&self) -> i32 { self.0.val() + self.1.val() } } // ОШИБКА: рекурсивный непрозрачный тип // fn eval(n: u32) -> impl Expr { // if n == 0 { Literal(0) } // else { Sum(Box::new(eval(n-1)), Box::new(Literal(1))) } // } // УСПЕШНО: Явная индирекция через Box<dyn Trait> fn eval(n: u32) -> Box<dyn Expr> { if n == 0 { Box::new(Literal(0)) } else { Box::new(Sum(eval(n-1), Box::new(Literal(1)))) } }
При проектировании парсера конфигураций для высокопроизводительного сетевого прокси мне необходимо было реализовать парсер рекурсивного спуска для вложенных выражений политики. Первоначальный дизайн предусматривал использование трейта Policy, представляющего разобранные правила, с функцией parse, которая должна была возвращать impl Policy, чтобы скрыть внутреннее представление узлов логики AND/OR/NOT от downstream-потребителей.
Первый подход включал прямую рекурсию: функция parse сопоставляла токены, и для составных выражений, таких как AND(policy1, policy2), она рекурсивно вызывала саму себя для разбора подпожалоб и возвращала их напрямую в виде impl Policy. Эта стратегия предлагала преимущества нулевых затрат абстракций через мономорфизацию и избегала накладных расходов на распределение в куче. Однако Rust выдал ошибку компиляции, утверждая, что рекурсивный вызов создает цикл, подразумевая бесконечный размер типа, поскольку конкретный возвращаемый тип должен был содержать вложенные экземпляры самого себя без ограничения.
Второе рассматриваемое решение заключалось в том, чтобы переключить тип возвращаемого значения на Box<dyn Policy>, что выделяло каждую рекурсивную подпожалобу в куче и возвращало только жирный указатель объекта трейта. Этот подход успешно скомпилировался, так как тип возвращаемого значения теперь был указателем фиксированного размера независимо от глубины вложенности. Однако это вводило накладные расходы на распределение в куче для каждого узла в дереве разбора и требовало динамической диспетчеризации через vtable во время оценки политики.
Третий альтернативный подход заключался в определении явного enum PolicyNode с вариантами Literal, And, Or и Not, где рекурсивные варианты оборачивали себя в Box<PolicyNode>, избегая dyn диспетчеризации, но требуя закрытого набора типов узлов, которые известны во время компиляции. Этот подход с статической диспетчеризацией устранял накладные расходы vtable и расходы на выделение, связанные с объектами трейтов, хотя и жертвовал возможностью для downstream-пакетов расширить язык политики новыми типами узлов без изменения определения enum.
Мы выбрали подход Box<dyn Policy>, потому что движок политики требовал регистрации плагинов в runtime, где сторонние расширения могли бы определять новые типы политик, что делало закрытый enum непрактичным для расширяемости. Результатом стал функциональный рекурсивный парсер, который обменивал стековое пространство на стабильность кучи и динамическую гибкость, хотя позже мы оптимизировали «горячие» пути, преобразовав рекурсивные паттерны разбора в итеративные циклы для снижения давления выделения в сценариях с высоким пропуском.
Как async fn влияет на ограничения рекурсии, учитывая, что он также возвращает непрозрачный impl Future?
async fn десугарируется в состояние машины, реализующее Future, где каждая точка .await представляет собой отдельное состояние приостановки, требующее хранения в сгенерированном enum. Рекурсивные вызовы async fn вызывают ту же ошибку бесконечного типа, потому что сгенерированное будущее будет содержать себя в качестве варианта, нарушая ограничение Sized. Кандидаты часто предполагают, что компилятор автоматически обрабатывает асинхронную рекурсию, но решение требует вручную упаковки будущего, используя Box::pin или возвращения Pin<Box<dyn Future<Output = T>>>>, что заставляет выделение памяти и фиксирует рекурсивное будущее на определенном месте в памяти. Это вводит дополнительную сложность обеспечения того, чтобы возвращаемое будущее оставалось 'static или правильно ограниченным, и понимания того, что рекурсия async fn следует тем же правилам Sized, что и стандартные возвраты impl Trait.
Почему использование impl Trait в позиции аргумента (APIT) не вызывает аналогичных ограничений рекурсии?
impl Trait в позиции аргумента является синтаксическим сахаром для анонимного параметра обобщения, ограниченного указанным трейт. Когда функция рекурсивно вызывает саму себя с APIT, компилятор генерирует отдельный мономорфизированный экземпляр для каждого конкретного типа, переданного на каждой позиции вызова, что означает, что рекурсивная функция не возвращает непрозрачную версию самой себя, а принимает разные конкретные типы на каждом уровне стека. Кандидаты часто путают RPIT и APIT, не осознавая, что APIT участвует в мономорфизации на графе вызовов, где тип возвращаемого значения (если он конкретен для каждой инстанции) известен, в то время как RPIT определяет единственный непрозрачный тип для тела функции, который не может разрешиться в само-ссылающую бесконечную структуру без индирекции.
Может ли impl Trait использоваться рекурсивно, если он обернут в структуру, такую как Wrapper<T>(T), где T: Trait?
Структура, содержащая impl Trait в качестве поля, не может быть названа напрямую, потому что impl Trait действителен только в позициях возврата функций или позициях аргументов, а не в определениях типов или полях структур. Кандидаты часто пытаются написать Box<impl Trait>, что является неверным синтаксисом вне контекстов возврата функций, путая непрозрачный тип-алитек с конструктором конкретного типа. Это недопонимание возникает из-за восприятия impl Trait как типа первого класса, который можно использовать в позициях обобщения, вместо понимания его как экзистенциального типа, генерируемого компилятором и доступного только в специфических позициях сигнатуры функции. Правильный подход требует либо Box<dyn Trait> для стирания типов, либо определения рекурсивного перечисления, где конкретный тип явен, что гарантирует, что система типов может вычислить ограничение Sized до выполнения программы.