You can cheese infinite loop detection by setting a max number of edge traversals (that way you don't just loop longer when someone speeds up the happy path).
For real code, you wouldn't generate a web page with 5 million entries in it, so you can be pretty sure that the data is bad even if it's not cyclical (but it probably is)
These are not emacs commands. They aren't even unix shell commands. They are TTY commands, some of them dating back to the dot matrix teletype terminals.
My favorite is ^U, which 90% of the time lets you start over on a password prompt when you are sure you just fat fingered but not sure how badly.
Thank you, that one is really useful! The one I had always remembered was ^H for whenever no other way to delete characters works. I need it in some SQL REPLs which aren't configurable.
I think you might be conflating these (or maybe I should say the gp is). Nevertheless.
Do you have a reference to the history of key combos like ctrl f, b, n, p and a and e? Those are typically referred to as emacs style navigation and I am genuinely unaware of history of those as common tty control codes outside of emacs for cursor movement. They weren’t dec vt control codes. Ctrl-U was though and even has ASCII assignment as “NAK”. Ctrl-H and C are similar.. but people don’t typically refer to those as “emacs” keys.
> Do you have a reference to the history of key combos like ctrl f, b, n, p and a and e? Those are typically referred to as emacs style navigation and I am genuinely unaware of history of those as common tty control codes outside of emacs for cursor movement.
I've always heard of it as an ASCII control character and gets its history from Unix interpretations of really old IBM keyboards which got its history from typewriters. I've literally never used emacs for anything other than ^X to exit; I'd rather use cat than emacs. I use vim. But ^H has worked for me as intended on a serial console and on telnet.
Some diving through wikipedia:
[0] says: Pressing the backspace key on a computer terminal would generate the ASCII code 08, BS or Backspace, a control code which would delete the preceding character. That control code could also be accessed by pressing Control-H, as H is the eighth letter of the Latin alphabet.
[1] says: In some typewriters, a typist would, for example, type a lowercase letter A with acute accent (á) by typing a lowercase letter A, backspace, and then the acute accent key. This technique (also known as overstrike) is the basis for such spacing modifiers in computer character sets such as the ASCII caret (^, for the circumflex accent).
[2] says: Unix (command line and programs using readline): Ctrl+H = Delete previous character
[3] supports [0] and says: Caret notation is a notation for control characters in ASCII. The notation assigns ^A to control-code 1, sequentially through the alphabet to ^Z assigned to control-code 26 (0x1A). Often a control character can be typed on a keyboard by holding down the Ctrl and typing the character shown after the caret.
However, it's worth noting that it also says The meaning or interpretation of, or response to the individual control-codes is not prescribed by the caret notation.
But, despite that, ASCII describes control character 8 as backspace [4] [5].
According to this Wikipedia article, work on ASCII began in 1960 and its first release in 1963 [6].
Emacs' first release was in 1985 [7].
I suggest that perhaps in your bubble control sequences are referred to as emacs style navigation even if it's not necessarily the most historically accurate. I'm glad you're working with *nix enough to be familiar with emacs and there's always new old things to learn. There's a lot of history to learn and understand.
I read your post and thought, "I've misremembered the story."
But the Wikipedia page for the Teletype-33 claims that it 1) had control characters, and 2) was inspiration for some of the ASCII character set, which was defined later in the same year:
1) If it‘s a tree, it ain‘t got no loops
2) The stack isn‘t to deal with loops, the „visited“ flag at each edge is there for that. The stack (for DFS, BFS would be a queue) is there to keep track of which nodes have been visited such that you can construct a path from the starting node to the one you‘re looking for.
Obviously there are variants to this, depending on what you‘re actually trying to achieve with it. My point is that a stack would be a very inefficient way to deal with loops.
1) you're right, I edited my message to reflect that I meant a graph traversal algorithm.
2) a visited flag on an edge? That won't support simultaneous traversals. Keeping a stack is a lot more efficient than permitting only one traversal at a time.
I‘m not sure why you‘re bringing concurrency to the table.
My point still is that looking something up in a stack (did I visit this node?) costs O(n) time, so the BFS will degrade from O(m+n) to O(m*n+n).
To come back to the concurrency, if you can index your edges in some way, you can also store the visited flag in a separate datastracture to support concurrent access (one „flag store“ for each access).
