Jako programista z pewnością znasz błąd przepełnienia stosu z powodu oczywistej rekurencji. Ale z pewnością istnieje wiele dziwnych i niezwykłych sposobów, aby Twój ulubiony język wypluł ten błąd.

Cele:

1. Musi spowodować przepełnienie stosu, które jest wyraźnie widoczne na wyjściu błędu.
2. Nie wolno używać oczywistej rekurencji.

Przykłady nieprawidłowych programów:

// Invalid, direct obvious recursion.
methodA(){ methodA(); }

// Invalid, indirect, but obvious recursion.
methodA(){ methodB(); }
methodB(){ methodA(); }

Najbardziej kreatywne sposoby są najlepsze, ponieważ jest to konkurs popularności . Tj. Unikaj nudnych oczywistych odpowiedzi takich jak to:

throw new StackOverflowError(); // Valid, but very boring and downvote-deserving.

Mimo że teraz zaakceptowałem odpowiedź, dodawanie kolejnych odpowiedzi jest nadal w porządku :)

Pyton

import sys
sys.setrecursionlimit(1)

Spowoduje to natychmiastową awarię tłumacza:

$ cat test.py
import sys
sys.setrecursionlimit(1)
$ python test.py
Exception RuntimeError: 'maximum recursion depth exceeded' in <function _remove at 0x10e947b18> ignored
Exception RuntimeError: 'maximum recursion depth exceeded' in <function _remove at 0x10e8f6050> ignored
$ 

Zamiast używać rekurencji, po prostu zmniejsza stos, aby natychmiast się przepełnił.

Pyton

import webbrowser
webbrowser.open("http://stackoverflow.com/")

C / Linux 32bit

void g(void *p){
        void *a[1];
        a[2]=p-5;
}
void f(){
        void *a[1];
        g(a[2]);
}
main(){
        f();
        return 0;
}

Działa poprzez nadpisanie adresu zwrotnego, więc gwraca do punktu mainprzed wezwaniem f. Działa na każdej platformie, na której stos zwrotny znajduje się na stosie, ale może wymagać poprawek.

Oczywiście pisanie poza tablicą jest nieokreślonym zachowaniem i nie masz żadnej gwarancji, że spowoduje to przepełnienie stosu, zamiast, powiedzmy, pomalować wąsy na niebiesko. Duże znaczenie mogą mieć szczegóły flag platformy, kompilatora i kompilacji.

JavaScript / DOM

with (document.body) {
    addEventListener('DOMSubtreeModified', function() {
        appendChild(firstChild);
    }, false);

    title = 'Kill me!';
}

Jeśli chcesz zabić swoją przeglądarkę, wypróbuj to w konsoli.

Jawa

Widziałem coś takiego gdzieś tutaj:

Edycja: Znaleziono tam, gdzie go widziałem: odpowiedź Joe K na najkrótszy program, który generuje błąd StackOverflow

public class A {
    String val;
    public String toString() {
        return val + this;
    }

    public static void main(String[] args) {
        System.out.println(new A());
    }
}

To może mylić niektórych początkujących w Javie. Po prostu ukrywa połączenie rekurencyjne. val + thisstaje się, val + this.toString()ponieważ valjest ciągiem.

Zobacz, jak działa tutaj: http://ideone.com/Z0sXiD

do

Raczej latwo:

int main()
{
    int large[10000000] = {0};
    return 0;
}

Przepełnienie stosu nierekurencyjnego w C

Niezgodność konwencji wywoływania.

typedef void __stdcall (* ptr) (int);

void __cdecl hello (int x) { }

void main () {
  ptr goodbye = (ptr)&hello;
  while (1) 
    goodbye(0);
}

Kompiluj z gcc -O0.

__cdeclfunkcje oczekują od wywołującego wyczyszczenia stosu i __stdcalloczekują od odbierającego, więc przez wywołanie wskaźnika funkcji typecast czyszczenie nigdy się mainnie kończy - wypycha parametr na stos dla każdego wywołania, ale nic go nie wyrywa i ostatecznie wypełnienia stosu.

JavaScript

window.toString = String.toLocaleString;
+this;

Byłem sfrustrowany faktem, że java 7 i java 8 są odporne na mój zły kod w mojej poprzedniej odpowiedzi . Uznałem więc, że łatka do tego jest konieczna.

Powodzenie! Zrobiłem printStackTrace()rzut StackOverflowError. printStackTrace()jest powszechnie używany do debugowania i logowania i nikt nie podejrzewa, że ​​może to być niebezpieczne. Nietrudno zauważyć, że ten kod może zostać wykorzystany do stworzenia poważnych problemów bezpieczeństwa:

public class StillMoreEvilThanMyPreviousOne {
    public static void main(String[] args) {
        try {
            evilMethod();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void evilMethod() throws Exception {
        throw new EvilException();
    }

    public static class EvilException extends Exception {
        @Override
        public Throwable getCause() {
            return new EvilException();
        }
    }
}

Niektórzy ludzie mogą myśleć, że jest to oczywista rekurencja. Nie jest. EvilExceptionKonstruktor nie wywołuje getCause()metodę, tak że wyjątek może być faktycznie rzucony bezpiecznie po wszystkim. Wywołanie getCause()metody nie spowoduje żadnego z StackOverflowErrornich. Rekurencja znajduje się w normalnie nieoczekiwanym printStackTrace()zachowaniu JDK i dowolnej bibliotece innej firmy do debugowania i rejestrowania, która służy do sprawdzania wyjątku. Ponadto prawdopodobne jest, że miejsce, w którym wyjątek jest zgłaszany, znajduje się bardzo daleko od miejsca, w którym jest przetwarzany.

W każdym razie, oto kod, który generuje a StackOverflowErrori nie zawiera w końcu żadnych rekurencyjnych wywołań metod. StackOverflowErrorDzieje poza mainmetody, w JDK na UncaughtExceptionHandler:

public class StillMoreEvilThanMyPreviousOneVersion2 {
    public static void main(String[] args) {
        evilMethod();
    }

    private static void evilMethod() {
        throw new EvilException();
    }

    public static class EvilException extends RuntimeException {
        @Override
        public Throwable getCause() {
            return new EvilException();
        }
    }
}

Exception: java.lang.StackOverflowError thrown from the UncaughtExceptionHandler in thread "main"

Linux NASM x86

section .data
    helloStr:     db 'Hello world!',10 ; Define our string
    helloStrLen:  equ $-helloStr       ; Define the length of our string

section .text
    global _start

    doExit:
        mov eax,1 ; Exit is syscall 1
        mov ebx,0 ; Exit status for success
        int 80h   ; Execute syscall

    printHello:
        mov eax,4           ; Write syscall is No. 4
        mov ebx,1           ; File descriptor 1, stdout
        mov ecx,helloStr    ; Our hello string
        mov edx,helloStrLen ; The length of our hello string
        int 80h             ; execute the syscall

    _start:
        call printHello ; Print "Hello World!" once
        call doExit     ; Exit afterwards

Spojler:

Zapominając o powrocie z printHello, więc wskakujemy od razu do _start.

C ++ w czasie kompilacji

template <unsigned N>
struct S : S<N-1> {};

template <>
struct S<0> {};

template
struct S<-1>;

$ g ++ -c test.cc -ftemplate-depth = 40000
g ++: wewnętrzny błąd kompilatora: błąd segmentacji (program cc1plus)
Prześlij pełny raport o błędzie,
w razie potrzeby ze wstępnie przetworzonym źródłem.
Zobacz instrukcje.

Ten plik źródłowy nie ma rekurencji, żadna z klas nie ma się jako klasa podstawowa, nawet pośrednio. (W C ++, w takiej klasie szablonów S<1>i S<2>są to zupełnie odrębne klasy.) Błąd segmentacji wynika z przepełnienia stosu po rekurencji w kompilatorze.

Bash (Danger Alert)

while true
do 
  mkdir x
  cd x
done

Ściśle mówiąc, nie spowoduje to bezpośredniego przepełnienia stosu, ale generuje coś, co może być oznaczone jako „ trwała sytuacja generowania przepełnienia stosu ”: gdy uruchomisz to, aż dysk będzie pełny i chcesz usunąć bałagan za pomocą „rm -rf x ”, ten został trafiony.

Jednak nie dzieje się tak na wszystkich systemach. Niektóre są bardziej wytrzymałe niż inne.

Duże niebezpieczeństwo OSTRZEŻENIE:

niektóre systemy radzą sobie z tym bardzo źle i możesz mieć bardzo trudny czas do czyszczenia (ponieważ sam „rm -rf” napotka problem z reusion). Być może będziesz musiał napisać podobny skrypt do czyszczenia.

Lepiej spróbuj tego na maszynie wirtualnej typu scratch, jeśli nie jesteś pewien.

PS: to samo dotyczy oczywiście, jeśli jest zaprogramowane lub wykonane w skrypcie wsadowym.
PPS: uzyskanie komentarza od ciebie może być interesujące, jak zachowuje się twój system ...

Jawa

Fajny od Java Puzzlers . Co to drukuje?

public class Reluctant {
    private Reluctant internalInstance = new Reluctant();

    public Reluctant() throws Exception {
        throw new Exception("I'm not coming out");
    }

    public static void main(String[] args) {
        try {
            Reluctant b = new Reluctant();
            System.out.println("Surprise!");
        } catch (Exception ex) {
            System.out.println("I told you so");
        }
    }
}

W rzeczywistości kończy się niepowodzeniem w przypadku StackOverflowError.

Wyjątkiem w konstruktorze jest tylko czerwony śledź. Oto co mówi o tym książka:

Po wywołaniu konstruktora inicjalizatory zmiennych instancji działają przed treścią konstruktora . W takim przypadku inicjalizator zmiennej internalInstancewywołuje rekursywnie konstruktor. Z kolei ten konstruktor inicjuje własne internalInstancepole, wywołując ponownie konstruktor niechętny i tak dalej, ad infinitum. Te rekurencyjne wywołania powodują, StackOverflowErrorże ciało konstruktora kiedykolwiek ma szansę wykonać. Ponieważ StackOverflowErrorjest to podtyp, Errora nie Exceptionklauzula catch w nim mainnie łapie.

Lateks

\end\end

Stos wejściowy przepełnia się, ponieważ \endwielokrotnie rozwija się w nieskończonej pętli, jak wyjaśniono tutaj .

TeX nie działa z TeX capacity exceeded, sorry [input stack size=5000]podobnym lub podobnym.

BF

W końcu przepełni stos, zależy tylko od tego, jak długo interpreter utworzy stos ...

+[>+]

C #, w czasie kompilacji

Istnieje wiele sposobów, aby kompilator Microsoft C # wysadził stos; za każdym razem, gdy zobaczysz błąd „wyrażenie jest zbyt skomplikowane, aby go skompilować” z kompilatora C #, który prawie na pewno jest spowodowany przepaleniem stosu.

Analizator składni jest zejściem rekurencyjnym, więc każda wystarczająco głęboko zagnieżdżona struktura języka zniszczy stos:

 class C { class C { class C { ....

Parser wyrażeń jest dość sprytny w eliminowaniu rekurencji po stronie, która jest często powtarzana. Zazwyczaj:

x = 1 + 1 + 1 + 1 + .... + 1;

który buduje niezwykle głębokie drzewo parsowania, nie wysadzi stosu. Ale jeśli wymusisz rekurencję po drugiej stronie:

x = 1 + (1 + (1 + (1 + ....+ (1 + 1))))))))))))))))))))))))))))))))))))))))))...;

wtedy stos może zostać zdmuchnięty.

Mają one nieelegacyjną właściwość, że program jest bardzo duży. Możliwe jest również włączenie analizatora semantycznego w nieograniczoną rekurencję za pomocą małego programu, ponieważ nie jest on wystarczająco inteligentny, aby usunąć pewne nieparzyste cykle w systemie typów. (Roslyn może to poprawić.)

public interface IN<in U> {}
public interface IC<X> : IN<IN<IC<IC<X>>>> {}
...
IC<double> bar = whatever;
IN<IC<string>> foo = bar;  // Is this assignment legal? 

W tym miejscu opisuję, dlaczego ta analiza przechodzi w nieskończoną rekurencję:

http://blogs.msdn.com/b/ericlippert/archive/2008/05/07/covariance-and-contravariance-part-twelve-to-infinity-but-not-beyond.aspx

i dla wielu bardziej interesujących przykładów powinieneś przeczytać ten artykuł:

http://research.microsoft.com/en-us/um/people/akenn/generics/FOOL2007.pdf

W Internecie (z którego korzysta miliard osób dziennie)

Redirects, HTTP status code: 301

Na przykład w witrynie pomocy technicznej firmy Dell (bez obrazy, przepraszam, Dell):

Jeśli usuniesz TAG obsługi z adresu URL, przejdzie on w nieskończone przekierowania . W następującym adresie URL ###### jest dowolnym tagiem pomocniczym.

http://www.dell.com/support/drivers/uk/en/ukdhs1/ServiceTag/######?s=BSD&~ck=mn

Uważam, że jest to równoważne z przepełnieniem stosu.

PHP

Przepełnienie stosu wykonane tylko z zapętlonymi elementami.

$a = array(&$a);
while (1) {
    foreach ($a as &$tmp) {
        $tmp = array($tmp, &$a);
    }
}

Objaśnienie (najedź kursorem, aby zobaczyć spoiler):

Program przełączy się na błąd, gdy interpreter spróbuje wyrzucić śmieci do $tmptablicy (podczas ponownego przypisywania $tmptutaj). Tylko dlatego, że tablica jest zbyt głęboka (samoreferencja), a następnie moduł wyrzucania elementów bezużytecznych kończy się rekurencją.

Jawa

Zrobiłem dokładnie odwrotnie - program, który oczywiście powinien zgłaszać błąd przepełnienia stosu, ale tego nie robi.

public class Evil {
    public static void main(String[] args) {
        recurse();
    }

    private static void recurse() {
        try {
            recurse();
        } finally {
            recurse();
        }
    }
}

Wskazówka: program działa w czasie O (2 ⁿ ), a n jest rozmiarem stosu (zwykle 1024).

Z Java Puzzlers # 45:

Załóżmy, że nasza maszyna może wykonywać 10 ¹⁰ połączeń na sekundę i generować 10 ¹⁰ wyjątków na sekundę, co jest dość hojne jak na obecne standardy. Zgodnie z tymi założeniami program zakończy się za około 1,7 × 10 ²⁹¹ lat. Mówiąc z perspektywy czasu, żywotność naszego Słońca szacuje się na 10 ¹⁰ lat, więc jest bezpieczny zakład, że nikt z nas nie będzie w pobliżu, aby zakończyć ten program. Chociaż nie jest to nieskończona pętla, równie dobrze może być.

DO#

Pierwszy post, więc spokojnie.

class Program
{
    static void Main()
    {
        new System.Diagnostics.StackTrace().GetFrame(0).GetMethod().Invoke(null, null);
    }
}

To po prostu tworzy ślad stosu, chwyta górną ramkę (która będzie naszym ostatnim wywołaniem Main()), pobiera metodę i wywołuje ją.

Jawa

• W Javie 5 printStackTrace()wchodzi w nieskończoną pętlę.
• W Javie 6 printStackTrace()rzuca StackOverflowError.
• W Javie 7 i 8 zostało to naprawione.

Szaloną rzeczą jest to, że w Javie 5 i 6 nie pochodzi ona od kodu użytkownika, dzieje się to w kodzie JDK. Nikt nie ma podejrzeń, printStackTrace()których wykonanie byłoby niebezpieczne.

public class Bad {
    public static void main(String[] args) {
        try {
            evilMethod();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void evilMethod() throws Exception {
        Exception a = new Exception();
        Exception b = new Exception(a);
        a.initCause(b);
        throw a;
    }
}

JavaScript: Nierekurencyjna, iteracyjna mutacja funkcji

var f = function() {
    console.log(arguments.length);
};

while (true) {
    f = f.bind(null, 1);
    f();
}

W ogóle nie ma tu rekurencji. fbędzie wielokrotnie curry z coraz większą liczbą argumentów, aż będzie mógł przepełnić stos w jednym wywołaniu funkcji. Ta console.logczęść jest opcjonalna, jeśli chcesz zobaczyć, ile argumentów potrzeba, aby to zrobić. Zapewnia również, że sprytne silniki JS nie zoptymalizują tego.

Wersja Code-golf w CoffeeScript, 28 znaków:

f=->
do f=f.bind f,1 while 1

C # z epicką porażką

using System.Xml.Serialization;

[XmlRoot]
public class P
{
    public P X { get { return new P(); } set { } }
    static void Main()
    {
        new XmlSerializer(typeof(P)).Serialize(System.Console.Out, new P());
    }
}

Sposób, w jaki zawodzi, jest epicki, całkowicie zaskoczył mnie:

To tylko jedna klatka z pozornie nieskończonej serii dziwnych zdjęć.

To musi być najdziwniejsza rzecz na świecie. Czy ktoś może wyjaśnić? Najwyraźniej coraz większa liczba spacji wykorzystywanych do wcięć powoduje pojawienie się białych bloków. Zdarza się to na Win7 Enterprise x64 z .NET 4.5.

Właściwie nie widziałem jeszcze końca. Jeśli zastąpi System.Console.Outsię System.IO.Stream.Null, że dość szybko umiera.

Wyjaśnienie jest dość proste. Tworzę klasę, która ma jedną właściwość i zawsze zwraca nową instancję tego typu zawierającego. Jest to więc nieskończenie głęboka hierarchia obiektów. Teraz potrzebujemy czegoś, co próbuje to odczytać. Tam właśnie używam XmlSerializer, co właśnie to robi. I najwyraźniej wykorzystuje rekurencję.

grzmotnąć

_(){ _;};_

Choć wielu może uznać, że rekurencja jest oczywista , ale wydaje się ładna. Nie?

Po wykonaniu masz gwarancję, że zobaczysz:

Segmentation fault (core dumped)

Haskell

(smutne, ale prawdziwe, przynajmniej dopóki ghc-7.6, chociaż z O1lub więcej to zoptymalizuje problem)

main = print $ sum [1 .. 100000000]

Pogawędka

To tworzy nową metodę w locie, która
  tworzy nową metodę w locie, która
    tworzy nową metodę w locie, która
      ...
    ...
  ..
a następnie zostaje przeniesiona na nią.

Dodatkowa mała przyprawa pochodzi z jednoczesnego stresowania pamięci stosu i pamięci stosu, tworząc zarówno dłuższą i dłuższą nazwę metody, jak i ogromną liczbę jako odbiornik, gdy spadamy z dziury ... (ale rekurencja uderza nas pierwsza ).

skompiluj w liczbie całkowitej:

downTheRabbitHole
    |name deeperName nextLevel|

    nextLevel := self * 2.
    name := thisContext selector.
    deeperName := (name , '_') asSymbol.
    Class withoutUpdatingChangesDo:[
        nextLevel class 
            compile:deeperName , (thisContext method source copyFrom:name size+1).
    ].
    Transcript show:self; showCR:' - and down the rabbit hole...'.
    "/ self halt. "/ enable for debugging
    nextLevel perform:deeperName.

następnie skacz, oceniając "2 downTheRabbitHole"...
... po chwili skończysz w debuggerze, pokazując wyjątek RecursionException.

Następnie musisz wyczyścić cały bałagan (zarówno SmallInteger, jak i LargeInteger mają teraz dużo kodu z krainy czarów):

{SmallInteger . LargeInteger } do:[:eachInfectedClass |
    (eachInfectedClass methodDictionary keys 
        select:[:nm| nm startsWith:'downTheRabbitHole_'])
            do:[:each| eachInfectedClass removeSelector:each]

albo spędzić trochę czasu w przeglądarce, usuwając krainę Alicji.

Oto niektóre z głowy śladu:

2 - and down the rabbit hole...
4 - and down the rabbit hole...
8 - and down the rabbit hole...
16 - and down the rabbit hole...
[...]
576460752303423488 - and down the rabbit hole...
1152921504606846976 - and down the rabbit hole...
2305843009213693952 - and down the rabbit hole...
[...]
1267650600228229401496703205376 - and down the rabbit hole...
2535301200456458802993406410752 - and down the rabbit hole...
5070602400912917605986812821504 - and down the rabbit hole...
[...]
162259276829213363391578010288128 - and down the rabbit hole...
324518553658426726783156020576256 - and down the rabbit hole...
[...]
and so on...

PS: dodano „withoutUpdatingChangesFile:”, aby uniknąć konieczności czyszczenia trwałego pliku dziennika zmian Smalltalk.

PPS: dzięki za wyzwanie: myślenie o czymś nowym i innowacyjnym było zabawą!

PPPS: Chciałbym zauważyć, że niektóre dialekty / wersje Smalltalk kopiują przepełnione ramki stosu na stos - więc mogą one zamiast tego wystąpić w sytuacji braku pamięci.

DO#

Naprawdę duży struct, bez rekurencji, czysty C #, niezabezpieczony kod.

public struct Wyern
{
    double a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
public struct Godzilla
{
    Wyern a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
public struct Cyclops
{
    Godzilla a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
public struct Titan
{
    Cyclops a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
}
class Program
{
    static void Main(string[] args)
    {
        // An unhandled exception of type 'System.StackOverflowException' occurred in ConsoleApplication1.exe
        var A=new Titan();
        // 26×26×26×26×8 = 3655808 bytes            
        Console.WriteLine("Size={0}", Marshal.SizeOf(A));
    }
}

jako kicker powoduje awarię okien debugowania stwierdzając, że {Cannot evaluate expression because the current thread is in a stack overflow state.}

I wersja ogólna (dzięki za sugestię NPSF3000)

public struct Wyern<T>
    where T: struct
{
    T a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;        
}


class Program
{
    static void Main(string[] args)
    {
        // An unhandled exception of type 'System.StackOverflowException' occurred in ConsoleApplication1.exe
        var A=new Wyern<Wyern<Wyern<Wyern<int>>>>();
    }
}

DO#

Wadliwe wdrożenie nadpisanego ==operatora:

public class MyClass
{
    public int A { get; set; }

    public static bool operator ==(MyClass obj1, MyClass obj2)
    {
        if (obj1 == null)
        {
            return obj2 == null;
        }
        else
        {
            return obj1.Equals(obj2);
        }
    }

    public static bool operator !=(MyClass obj1, MyClass obj2)
    {
        return !(obj1 == obj2);
    }

    public override bool Equals(object obj)
    {
        MyClass other = obj as MyClass;
        if (other == null)
        {
            return false;
        }
        else
        {
            return A == other.A;
        }
    }
}

Można powiedzieć, że to oczywiste, że operator==wywołuje się za pomocą ==operatora, ale zwykle nie myślisz w ten sposób ==, więc łatwo wpaść w tę pułapkę.

Uruchamianie odpowiedzi przy użyciu SnakeYAML

class A
{

    public static void main(String[] a)
    {
         new org.yaml.snakeyaml.Yaml().dump(new java.awt.Point());
    }
}

Edycja: odkopano go

Od czytelnika zależy, jak to działa: P (wskazówka: stackoverflow.com)

Nawiasem mówiąc: rekurencja jest wykonywana dynamicznie przez SnakeYAML (zauważysz, jeśli wiesz, jak wykrywa pola, które serializuje, i patrzy na Pointkod źródłowy)

Edycja: mówiąc, jak to działa:

SnakeYAML szuka pary getXXXi setXXXmetod o tej samej nazwie, XXXa zwracany typ gettera jest taki sam jak parametr settera; i, co zaskakujące, Pointklasa ma Point getLocation()a, void setLocation(Point P)które zwraca się; SnakeYAML tego nie zauważa i powtarza się w tym dziwactwie i przepływach StackOver. Odkryłem to podczas pracy z nimi w HashMapai pytaniu na stackoverflow.com.

DO#

niepoprawnie zaimplementowany moduł pobierania właściwości

class C
{
   public int P { get { return P; } }
}

static void Main()
{
   int p = new C().P;
}