How to implement alternation?

A stack of input-positions seems to be necessary, in order to deal with nested alternations. It seems to me that either this alternation-stack has to be pushed on the repeat-stack or perhaps the opposite way around.

Conclusion: The repeat-stack must be pushed on the alternation-stack.. This way we can easily recover from a mismatch (flush eventual repeats from the mismatching pattern) and proceede with next pattern.

Alternation

Note that parentesis is used, but not yielding any groups.

/a(b|c)d/.match("acd")

R0R1R2R3R4R5R6R7R8R9
'a'ALTPAT'b'/PATPAT'c'/PAT/ALT'd'
I0I1I2
acd
input=I0  regex=R0  stack=[]
i.data == r.data == "a"→i+=1; r+=1
input=I1  regex=R1  stack=[]
r == AlternationOpen→r=r.find(PatternOpen)+1; alt.push(i)
input=I1  regex=R3  stack=[[I1 <>]]
i.data ("c") != r.data ("b")→try next alternation, r=r.find(PatternOpen)+1; i=alt[-1]
input=I1  regex=R6  stack=[[I1 <>]]
i.data == r.data == "c"→i+=1; r+=1
input=I2  regex=R7  stack=[[I1 <>]]
r == PatternClose→r=r.find(AlternationClose)+1; alt.pop
input=I2  regex=R9  stack=[]
i.data == r.data == "d"→i+=1; r+=1
input=I3  regex=R10  stack=[]
the end→nothing more to do

/a(bc|bd)e/.match("abde")

R0R1R2R3R4R5R6R7R8R9R10R11
'a'ALTPAT'b''c'/PATPAT'b''d'/PAT/ALT'e'
I0I1I2I3
abde
input=I0  regex=R0  stack=[]
i.data == r.data == "a"→i+=1; r+=1
input=I1  regex=R1  stack=[]
r == AlternationOpen→r=r.find(PatternOpen)+1; alt.push(i)
input=I1  regex=R3  stack=[[I1 <>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R4  stack=[[I1 <>]]
i.data ("d") != r.data ("c")→try next alternation, r=r.find(PatternOpen)+1; i = alt[-1]
input=I1  regex=R7  stack=[[I1 <>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R8  stack=[[I1 <>]]
i.data == r.data == "d"→i+=1; r+=1
input=I3  regex=R9  stack=[[I1 <>]]
r == PatternClose→r=r.find(AlternationClose)+1; alt.pop
input=I3  regex=R11  stack=[]
i.data == r.data == "e"→i+=1; r+=1
input=I4  regex=R12  stack=[]
the end→nothing more to do

/a(bc|b(d|e))f/.match("abef")

R0R1R2R3R4R5R6R7R8R9R10R11R12R13R14R15R16R17
'a'ALTPAT'b''c'/PATPAT'b'ALTPAT'd'/PATPAT'e'/PAT/ALT/ALT'e'
I0I1I2I3
abef
input=I0  regex=R0  stack=[]
i.data == r.data == "a"→i+=1; r+=1
input=I1  regex=R1  stack=[]
r == AlternationOpen→r=r.find(PatternOpen)+1; alt.push(i)
input=I1  regex=R3  stack=[[I1 <>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R4  stack=[[I1 <>]]
i.data ("e") != r.data ("c")→try next alternation, r=r.find(PatternOpen)+1; i = alt[-1]
input=I1  regex=R7  stack=[[I1 <>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R8  stack=[[I1 <>]]
r == AlternationOpen→r=r.find(PatternOpen)+1; alt.push(i)
input=I2  regex=R10  stack=[[I1 <>], [I2 <>]]
i.data ("e") != r.data ("d")→try next alternation, r=r.find(PatternOpen)+1; i = alt[-1]
input=I2  regex=R13  stack=[[I1 <>], [I2 <>]]
i.data == r.data == "e"→i+=1; r+=1
input=I3  regex=R14  stack=[[I1 <>], [I2 <>]]
r == PatternClose→r=r.find(AlternationClose)+1; alt.pop
input=I3  regex=R16  stack=[[I1 <>]]
r == AlternationClose→r+=1; alt.pop
input=I3  regex=R17  stack=[]
i.data == r.data == "e"→i+=1; r+=1
input=I4  regex=R18  stack=[]
the end→nothing more to do

/a(b*|bc)d/.match("abcd")

R0R1R2R3R4R5R6R7R8R9R10R11R12
'a'ALTPATREP'b'/REP/PATPAT'b''c'/PAT/ALT'd'
I0I1I2I3
abcd
input=I0  regex=R0  stack=[]
i.data == r.data == "a"→i+=1; r+=1
input=I1  regex=R1  stack=[]
r == AlternationOpen→r=r.find(PatternOpen)+1; alt.push(i)
input=I1  regex=R3  stack=[[I1 <>]]
r == RepeatOpen→r=r.find(RepeatClose)+1
input=I1  regex=R6  stack=[[I1 <I1_R4_N0_C0>]]
r == PatternClose→r=r.find(AlternationClose)+1
input=I1  regex=R12  stack=[[I1 <I1_R4_N0_C0>]]
i.data ("b") != r.data ("d")→restart at the repeat point; repeat-count+=1
input=I1  regex=R4  stack=[[I1 <I1_R4_N1_C0>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R5  stack=[[I1 <I1_R4_N1_C0>]]
r == RepeatClose→stack[-1].cnt += 1; r+=1
input=I2  regex=R6  stack=[[I1 <I1_R4_N1_C1>]]
r == PatternClose→r=r.find(AlternationClose)+1
input=I2  regex=R12  stack=[[I1 <I1_R4_N1_C1>]]
i.data ("c") != r.data ("d")→restart at the repeat point; repeat-count+=1
input=I1  regex=R4  stack=[[I1 <I1_R4_N2_C0>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R5  stack=[[I1 <I1_R4_N2_C0>]]
r == RepeatClose→stack[-1].cnt += 1; restart at repeat point
input=I2  regex=R4  stack=[[I1 <I1_R4_N2_C1>]]
i.data ("c") != r.data ("b")→stop (no more repeat is possible); pop off repeats; try next pattern
input=I1  regex=R8  stack=[[I1 <>]]
i.data == r.data == "b"→i+=1; r+=1
input=I2  regex=R9  stack=[[I1 <>]]
i.data == r.data == "c"→i+=1; r+=1
input=I3  regex=R10  stack=[[I1 <>]]
r == PatternClose→r=r.find(AlternationClose)+1; alt.pop
input=I3  regex=R12  stack=[]
i.data == r.data == "d"→i+=1; r+=1
input=I4  regex=R13  stack=[]
the end→nothing more to do