entityMap|0|type|LINK|mutability|MUTABLE|data|url|https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph/37455247#37455247|1|https://typescript-play.js.org/#code/KYOwrgtgBACgTgewMbAM6oMoBdgAcoDeAUFFBgCoCiMA%2BgIwA0JZVtATAIZOkXU1sAjbiz4BmIgF8iRLAE9cwKADUOAGwCWAEwBywAB5ZseADxH8%2BnCE2pYiFOjMA%2BKAF5CzANrxkaTDlwAdLy0dAC6AFy2Pg7%2BQaz8HFAAPlH2fnhxfIIA3J7eaWaZ7BwRqb6FwTSiuaReduWxlYKl%2BQ0ZldV59THt8aKlIMAAbsBwuRIeZqG5MvKK5ADuCGaoxgCyUBag1lAASsBICHCaxgDWwLIIAGZQawxQ55c3a47ObgRQHgDSUOogDxdrrdSmsPKCvqFQlAJLk5AooAAxBBgOArdabAzbGz7Q7HM6A573R5Al5vKCLZb%2BVYUtGk2FzMjqTGgWkYyw7HFHE7EwkAp63V6uRHI1FU4xIlG0170%2BEUgASYCscGAmgR6iucgwTNZWys2IOXPx-LufJJgrcWuZIDRzEtOBZYpeREcMzhim0CAAwrIkKo0MZmNo2VioIMRnAhfLFZplar1ZrtWLmKQPt9fv9Wj1cKUVBodBYzMYvs4pKRHHVouls86hVg4GBgLkgA|blocks|key|bub8o|text|哇，我喜欢这个问题。我不确定只使用类型系统是否有一种干净或正确的方法来做到这一点。|unstyled|depth|inlineStyleRanges|entityRanges|c8410|这里有一种不干净且可能不正确的方法:强制类型系统计算为每个状态启动状态机并运行它一些大量的步骤。如果每个可能的结束状态都是never，那么就没有循环。否则，要么是图中有圈，要么是图中有一些非常长的非循环路径。|offset|length|style|CODE|b1n7n|假设您有一个扩展了Record<keyof+M,+keyof+M>的对象类型M，这意味着M的值也是M的键。这描述了一个状态机(您在ValidNextStep的定义中有这样一个类型，但是您通过索引它来销毁它……不用担心，我们可以将其重建为{+[K+in+ProcessStep]:+ValidNextStep<K>+})。对于M的任何关键K，您可以计算一个步骤的M[K]、两个步骤的M[M[K]]或三个步骤的M[M[M[K]]]，依此类推。|4emec|我们可以非常快速地组合这些操作，以获得数量惊人的步骤：|apon2|type+TwoSteps<M+extends+Record<keyof+M,+keyof+M>>+=+{+[K+in+keyof+M]:+M[M[K]]+};
type+FourSteps<M+extends+Record<keyof+M,+keyof+M>>+=+TwoSteps<TwoSteps<M>>;
type+SixteenSteps<M+extends+Record<keyof+M,+keyof+M>>+=+FourSteps<FourSteps<M>>;
type+TwoHundredFiftySixSteps<M+extends+Record<keyof+M,+keyof+M>>+=+SixteenSteps<
++SixteenSteps<M>
>;|code-block|syntax|javascript|3iccd|如果编译器不对我大喊大叫，我只能做到这一步。|3t56t|然后，我们可以创建一个见证类型，如果检测到循环(或非常长的路径)，该类型会导致编译器错误：|8ebjd|type+NoCycles<
++N+extends+never+=+TwoHundredFiftySixSteps<
++++{+[K+in+ProcessStep]:+ValidNextStep<K>+}
++>[ProcessStep]
>+=+true;|8s5dt|对于您对ValidNextStep的原始定义来说，这很好，但如果我们将其更改为以下内容：|9jmcf|type+ValidNextStep<Step+extends+ProcessStep>+=+{
++[ProcessStep.STEP_1]:+ProcessStep.STEP_2a+%7C+ProcessStep.STEP_2b;
++[ProcessStep.STEP_2a]:+ProcessStep.STEP_3;
++[ProcessStep.STEP_2b]:+ProcessStep.STEP_3;
++[ProcessStep.STEP_3]:+ProcessStep.STEP_2a;+//+oops
}[Step];|bj9nt|则NoCycles定义会产生以下错误：|9knhm|//+Type+'ProcessStep.STEP_2a+%7C+ProcessStep.STEP_3'+does+not+satisfy+the+constraint+'never'.|fajrg|这表明，在运行了256个步骤之后，仍然可以处于STEP_2a或STEP_3中，这表示一个周期。|5prk8|这是个好主意吗？可能不会..。不能保证它是正确的，而且它可能会给编译器带来比保证更多的压力。但我不知道我想找更好的工作有多难。使用通用语言，您会尝试找到some+efficient+algorithm来检测循环，但TypeScript中的类型系统不太可能具有足够的表达能力来实现它。|9mq8a|因此，使用它的风险自负，祝你好运！|d3hr6|Link+to+code|1tnge^0|0|1P|5|0|9|O|12|1|18|1|1D|1|1T|D|3A|14|4I|1|4O|1|50|4|5A|7|5N|A|0|0|0|0|0|0|4|D|0|0|1|8|0|0|N|7|V|6|0|24|O|0|0|0|0|C|1|0^^$0|$1|$2|3|4|5|6|$7|8]]|9|$2|3|4|5|6|$7|A]]]|B|@$C|D|E|F|2|G|H|1M|I|@]|J|@]|6|$]]|$C|K|E|L|2|G|H|1N|I|@$M|1O|N|1P|O|P]]|J|@]|6|$]]|$C|Q|E|R|2|G|H|1Q|I|@$M|1R|N|1S|O|P]|$M|1T|N|1U|O|P]|$M|1V|N|1W|O|P]|$M|1X|N|1Y|O|P]|$M|1Z|N|20|O|P]|$M|21|N|22|O|P]|$M|23|N|24|O|P]|$M|25|N|26|O|P]|$M|27|N|28|O|P]|$M|29|N|2A|O|P]|$M|2B|N|2C|O|P]]|J|@]|6|$]]|$C|S|E|T|2|G|H|2D|I|@]|J|@]|6|$]]|$C|U|E|V|2|W|H|2E|I|@]|J|@]|6|$X|Y]]|$C|Z|E|10|2|G|H|2F|I|@]|J|@]|6|$]]|$C|11|E|12|2|G|H|2G|I|@]|J|@]|6|$]]|$C|13|E|14|2|W|H|2H|I|@]|J|@]|6|$X|Y]]|$C|15|E|16|2|G|H|2I|I|@$M|2J|N|2K|O|P]]|J|@]|6|$]]|$C|17|E|18|2|W|H|2L|I|@]|J|@]|6|$X|Y]]|$C|19|E|1A|2|G|H|2M|I|@$M|2N|N|2O|O|P]]|J|@]|6|$]]|$C|1B|E|1C|2|W|H|2P|I|@]|J|@]|6|$X|Y]]|$C|1D|E|1E|2|G|H|2Q|I|@$M|2R|N|2S|O|P]|$M|2T|N|2U|O|P]]|J|@]|6|$]]|$C|1F|E|1G|2|G|H|2V|I|@]|J|@$M|2W|N|2X|C|2Y]]|6|$]]|$C|1H|E|1I|2|G|H|2Z|I|@]|J|@]|6|$]]|$C|1J|E|1K|2|G|H|30|I|@]|J|@$M|31|N|32|C|33]]|6|$]]|$C|1L|E|-4|2|G|H|34|I|@]|J|@]|6|$]]]]

Wow I love this question. I'm not sure if there's a clean or correct way to do this using just the type system. 

Here's an unclean and possibly incorrect way: force the type system to go through the calculation of starting the state machine for every state and running it for some large number of steps. If every possible end state is <code>never</code>, then there are no cycles. Otherwise, there are either cycles or you have some really long acyclic paths in your graph. 

Imagine you have an object type <code>M</code> which extends <code>Record&lt;keyof M, keyof M&gt;</code>, meaning that the values of <code>M</code> are also keys of <code>M</code>. This describes a state machine (you have such a type inside your definition of <code>ValidNextStep</code> but you destroy it by indexing into it... don't worry, we can reconstruct it as <code>{ [K in ProcessStep]: ValidNextStep&lt;K&gt; }</code>). For any key <code>K</code> of <code>M</code> you can calculate <code>M[K]</code> for one step, or <code>M[M[K]]</code> for two steps, or <code>M[M[M[K]]]</code> for three steps, etc.

We can very quickly compose these operations to get crazy numbers of steps:

<pre><code>type TwoSteps&lt;M extends Record&lt;keyof M, keyof M&gt;&gt; = { [K in keyof M]: M[M[K]] };
type FourSteps&lt;M extends Record&lt;keyof M, keyof M&gt;&gt; = TwoSteps&lt;TwoSteps&lt;M&gt;&gt;;
type SixteenSteps&lt;M extends Record&lt;keyof M, keyof M&gt;&gt; = FourSteps&lt;FourSteps&lt;M&gt;&gt;;
type TwoHundredFiftySixSteps&lt;M extends Record&lt;keyof M, keyof M&gt;&gt; = SixteenSteps&lt;
 SixteenSteps&lt;M&gt;
&gt;;
</code></pre>

That's about as far as I can get without the compiler yelling at me.

Then we can make a witness type that causes a compiler error if a cycle (or a very long path) is detected:

<pre><code>type NoCycles&lt;
 N extends never = TwoHundredFiftySixSteps&lt;
 { [K in ProcessStep]: ValidNextStep&lt;K&gt; }
 &gt;[ProcessStep]
&gt; = true;
</code></pre>

That is fine for your original definition of <code>ValidNextStep</code>, but if we change it to the following:

<pre><code>type ValidNextStep&lt;Step extends ProcessStep&gt; = {
 [ProcessStep.STEP_1]: ProcessStep.STEP_2a | ProcessStep.STEP_2b;
 [ProcessStep.STEP_2a]: ProcessStep.STEP_3;
 [ProcessStep.STEP_2b]: ProcessStep.STEP_3;
 [ProcessStep.STEP_3]: ProcessStep.STEP_2a; // oops
}[Step];
</code></pre>

Then the <code>NoCycles</code> definition yields the following error:

<pre><code>// Type 'ProcessStep.STEP_2a | ProcessStep.STEP_3' does not satisfy the constraint 'never'.
</code></pre>

which shows that after running the machine for 256 steps it's still possible to be in either <code>STEP_2a</code> or <code>STEP_3</code>, which is indicative of a cycle.

Is this a good idea? Probably not... it is not guaranteed to be correct and it probably puts more strain on the compiler than is warranted. But I don't know how hard I'd want to try to find something better. With a general purpose language you'd try to find <a href="https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph/37455247#37455247">some efficient algorithm</a> to detect a cycle, but it's unlikely that the type system in TypeScript is expressive enough to implement it. 

So use that at your own risk, and good luck!

<a href="https://typescript-play.js.org/#code/KYOwrgtgBACgTgewMbAM6oMoBdgAcoDeAUFFBgCoCiMA+gIwA0JZVtATAIZOkXU1sAjbiz4BmIgF8iRLAE9cwKADUOAGwCWAEwBywAB5ZseADxH8+nCE2pYiFOjMA+KAF5CzANrxkaTDlwAdLy0dAC6AFy2Pg7+Qaz8HFAAPlH2fnhxfIIA3J7eaWaZ7BwRqb6FwTSiuaReduWxlYKl+Q0ZldV59THt8aKlIMAAbsBwuRIeZqG5MvKK5ADuCGaoxgCyUBag1lAASsBICHCaxgDWwLIIAGZQawxQ55c3a47ObgRQHgDSUOogDxdrrdSmsPKCvqFQlAJLk5AooAAxBBgOArdabAzbGz7Q7HM6A573R5Al5vKCLZb+VYUtGk2FzMjqTGgWkYyw7HFHE7EwkAp63V6uRHI1FU4xIlG0170+EUgASYCscGAmgR6iucgwTNZWys2IOXPx-LufJJgrcWuZIDRzEtOBZYpeREcMzhim0CAAwrIkKo0MZmNo2VioIMRnAhfLFZplar1ZrtWLmKQPt9fv9Wj1cKUVBodBYzMYvs4pKRHHVouls86hVg4GBgLkgA" rel="nofollow noreferrer">Link to code</a>

There's a multi-step process that I've implemented in my app as a state machine, and created types that express the possible state transitions:

<pre><code>enum ProcessStep {
 STEP_1,
 STEP_2a,
 STEP_2b,
 STEP_3
}
type ValidNextStep&lt;Step extends ProcessStep&gt; = {
 [ProcessStep.STEP_1]:
 | ProcessStep.STEP_2a
 | ProcessStep.STEP_2b;
 [ProcessStep.STEP_2a]: ProcessStep.STEP_3;
 [ProcessStep.STEP_2b]: ProcessStep.STEP_3;
 [ProcessStep.STEP_3]: never;
}[Step]
</code></pre>

But I'd like to be able to tell if I've created a cycle in this graph, i.e. if <code>ProcessStep.STEP_3</code> could transition back to <code>ProcessStep.STEP_2a</code>.

How might one go about establishing that kind of invariant at the type level? Seems tough, given that by default type aliases don't allow for circular references.

TS: Disallow cycles in types describing a state machine

TypeScript

编译器

有一个多步骤的过程，我在我的应用程序中实现了一个状态机，并创建了表示可能的状态转换的类型： enum ProcessStep { STEP_1, STEP_2a, STEP_2b, STEP_3}type ValidNextStep<Step extends ProcessStep> = { [Proces...

问TS:不允许在描述状态机的类型中使用循环
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问TS:不允许在描述状态机的类型中使用循环EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问TS:不允许在描述状态机的类型中使用循环
EN