Night Shift

Night Shift is a string-rewriting esolang invented by User:Hakerh400 in 2022.
== Syntax ==
Source code consists of zero or more rules, one rule per line.
Each rule consists of two patterns separated by -.
A pattern is a list of zero or more bits. Empty pattern is represented as /
== Rewriting rules ==
Input is a list of bits. Before the program starts, prepend 000 to the input. That is the main list of bits.
Repeat this process until the program halts.
Find the first position in the main list, such that there is a rule whose first pattern is a prefix of the main list starting from that position. If there are no such rule, halt. If there are multiple rules, pick the first one that appears in the source code. Replace the prefix (the first pattern) in the main list (on that position) with the second pattern from the rule. If it was the last rule from the source code, halt.
After the program halts, the main list is the output.
== Examples ==
We use string 1011 as the input in all examples to show step-by-step computation.
=== Cat program ===
Program:
 000 - /
Computation:
 1011
 0001011
 1011
=== Extract first bit ===
Program:
 0000 - 010010
 0001 - 110010
 00100 - 0010
 00101 - 0010
 0010 - 0011
 010011 - 0
 110011 - 1
Computation:
 1011
 0001011
 110010011
 11001011
 1100101
 110010
 110011
 1
=== Extract last bit ===
Program:
 00000 - 0000
 00001 - 0001
 00010 - 0000
 00011 - 0001
 0000 - 0
 0001 - 1
Computation:
 1011
 0001011
 000011
 00011
 0001
 1
=== Remove first bit ===
Program:
 0000 - 001
 0001 - 001
 001 - /
Computation:
 1011
 0001011
 001011
 011
=== Remove last bit ===
Program:
 00000 - 010000
 00001 - 010001
 00010 - 110000
 00011 - 110001
 0000 - 001
 0001 - 001
 01001 - 0010
 11001 - 0011
 001 - /
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 110111001
 11010011
 1100101
 001101
 101
=== Invert bits ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 001
 01001 - 0011
 11001 - 0010
 001 - /
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 11011111001
 1101110010
 110100100
 11001100
 0010100
 0100
=== Reverse bits ===
Program:
 0000 - 0101000
 0001 - 0111000
 000 - 00100
 0101010100100 - 0101001000101
 0101011100100 - 0111001000101
 0111010100100 - 0101001000111
 0111011100100 - 0111001000111
 010100100 - 110100101
 011100100 - 111100101
 0010101 - 0100101
 0010111 - 1100101
 00101 - 00100
 00100 - 0011
 11010011 - 00110
 11110011 - 00111
 0011 - /
Computation:
 1011
 0001011
 0111000011
 0111010100011
 0111010101110001
 0111010101110111000
 011101010111011100100
 011101010111001000111
 011101110010001010111
 011100100011101010111
 111100101011101010111
 111101001011101010111
 111101110010101010111
 111101110100101010111
 111101110101001010111
 111101110101010010111
 111101110101011100101
 111101110101011100100
 111101110111001000101
 111101110010001110101
 111111110010101110101
 111111110100101110101
 111111110111001010101
 111111110111010010101
 111111110111010100101
 111111110111010100100
 111111110101001000111
 111111111101001010111
 111111111101010010111
 111111111101011100101
 111111111101011100100
 111111111101111100101
 111111111101111100100
 11111111110111110011
 11111111110100111
 11111111001101
 11110011101
 00111101
 1101
=== Sort bits ===
Program:
 0000 - 0101000
 0001 - 0111000
 000 - 00100
 0101010100100 - 0101001000101
 0111010100100 - 0101001000111
 010100100 - 110100101
 011100100 - 111100101
 0010101 - 0100101
 0010111 - 1100101
 00101 - 001111
 1101001111 - 0011111101
 1111001111 - 0011111111
 001111 - 00100
 00100 - 00110
 0011001 - 0100110
 0011011 - 1100110
 00110 - 001110
 1101001110 - 0011100
 1111001110 - 0011101
 001110 - /
Computation:
 1011
 0001011
 0111000011
 0111010100011
 0111010101110001
 0111010101110111000
 011101010111011100100
 011101010111111100101
 0111010101111111001111
 0111010101110011111111
 011101010111001001111
 011101011111001011111
 011101011111110010111
 011101011111111100101
 0111010111111111001111
 0111010111110011111111
 0111010100111111111111
 011101010010011111111
 010100100011111111111
 110100101011111111111
 110101001011111111111
 110101110010111111111
 110101111100101111111
 110101111111001011111
 110101111111110010111
 110101111111111100101
 1101011111111111001111
 1101011111110011111111
 1101011100111111111111
 110101110010011111111
 110111110010111111111
 110111111100101111111
 110111111111001011111
 110111111111110010111
 110111111111111100101
 1101111111111111001111
 1101111111110011111111
 1101111100111111111111
 1101001111111111111111
 0011111101111111111111
 001001101111111111111
 001101101111111111111
 110011001111111111111
 110100110111111111111
 110111001101111111111
 110111110011011111111
 110111111100110111111
 110111111111001101111
 110111111111110011011
 110111111111111100110
 1101111111111111001110
 1101111111110011101
 1101111100111011
 1101001110111
 0011100111
 0111
=== Xor bits ===
Program:
 00000 - 0000
 00001 - 0001
 00010 - 0001
 00011 - 0000
 0000 - 0010
 0001 - 0011
 000 - 0010
 001 - /
Computation:
 1011
 0001011
 000111
 00001
 0001
 0011
 1
=== Increment binary number ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 0010
 010010 - 00111
 110010 - 00100
 0010 - 00111
 010011 - 00110
 110011 - 00111
 0011 - /
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 110111110010
 11011100100
 1101001000
 110011100
 00111100
 1100
=== Decrement binary number ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 0010
 110010 - 001100
 010010 - 00101
 0100110 - 001100
 1100110 - 001101
 00110 - 00111
 001110 - 00111
 00111 - /
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 110111110010
 110111001100
 11010011010
 1100110010
 001101010
 001111010
 1010
=== Remove zeros ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 001
 01001 - 001
 11001 - 0011
 001 - /
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 11011111001
 1101110011
 110100111
 1100111
 001111
 111
=== Remove ones ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 001
 01001 - 0010
 11001 - 001
 001 - /
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 11011111001
 110111001
 1101001
 110010
 0010
 0
=== Add n zeros after n-th one ===
Also removes input zeros.
Program:
 000 - 00101001001
 0010010 - 001001
 0010011 - 11001001
 001001 - 001101
 0010101 - 0100101
 0010111 - 1101001010011101
 00101001101 - 001111
 001110101 - 010011101
 001110111 - 11010011101
 0011101001101 - 001101
 01001111 - 0011110
 11001111 - 0011111
 001111 - /
Computation:
 1011
 0001011
 001010010011011
 0010111001001011
 1101001010011101001001011
 110100101001110100100111
 1101001010011101110010011
 110100101110100111010010011
 110111010010100111010100111010010011
 110111010010101001110100111010010011
 110111010100101001110100111010010011
 1101110101001010011101001110111001001
 110111010100101001110111010011101001001
 11011101010010111010011101010011101001001
 11011101011101001010011101010011101010011101001001
 11011101011101001010100111010011101010011101001001
 11011101011101010010100111010011101010011101001001
 11011101011101010010100111010100111010011101001001
 11011101011101010010101001110100111010011101001001
 11011101011101010100101001110100111010011101001001
 11011101011101010100101001110100111010011101001101
 1101110101110101010010100111010011101001101
 110111010111010101001010011101001101
 11011101011101010100101001101
 110111010111010101001111
 11011101011101010011110
 1101110101110100111100
 110111010111001111000
 11011101010011111000
 1101110100111101000
 110111001111001000
 11010011111001000
 1100111101001000
 001111101001000
 101001000
=== Check if there is the same number of zeros and ones ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 0010
 01110010 - 00110
 11010010 - 00110
 01010010 - 01001001
 11110010 - 11001011
 010010 - 00111
 110010 - 00111
 0010 - 1
 0011001 - 0100110
 0011011 - 1100110
 00110 - 0010
 001110 - 00111
 001111 - 00111
 00111 - 0
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 110111110010
 110111001011
 110011011
 111100110
 11110010
 11001011
 0011111
 001111
 00111
 0
=== Check if the input is a palindrome ===
Program:
 0000 - 01000
 0001 - 11000
 000 - 0010
 01010010 - 01001001
 01110010 - 11001001
 11010010 - 01001011
 11110010 - 11001011
 01001001 - 00110
 11001011 - 00110
 01001011 - 00111
 11001001 - 00111
 010010 - 1
 110010 - 1
 0010 - 1
 0011001 - 0100110
 0011011 - 1100110
 00110 - 0010
 001110 - 00111
 001111 - 00111
 00111 - 0
Computation:
 1011
 0001011
 11000011
 110100011
 1101110001
 11011111000
 110111110010
 110111001011
 111100100111
 110010110111
 001100111
 010011011
 011100110
 01110010
 11001001
 00111
 0
=== Truth machine ===
Program:
 0001 - 10001
 0000 - 0
== Implementation ==
Implementation in Haskell
Category:Languages
Category:Implemented
Category:2022
Category:String-rewriting_paradigm
Category:Turing complete