Sachverhalt:
A.
Die Staatsanwaltschaft Limmat/Albis warf A._ mit Strafbefehl vom 26. Juli 2018 vor, er habe sich am Bahnhof Glanzenberg in Dietikon aufgehalten, obwohl er mit Verfügung des Migrationsamts des Kantons Zürich vom 15. September 2017 mit einer Eingrenzung für das Gemeindegebiet Urdorf belegt worden sei. Sie bestrafte ihn deshalb wegen Missachtung der Ein- und Ausgrenzung im Sinne von Art. 119 Abs. 1 in Verbindung mit Art. 74 Abs. 1 und 2 AuG mit einer (unbedingten) Freiheitsstrafe von 90 Tagen (wovon 1 Tag durch Haft erstanden war). A._ erhob Einsprache.
B.
Das Bezirksgericht Dietikon bestätigte mit Urteil vom 9. Januar 2019 den Strafbefehl im Schuld- und Strafpunkt, wobei es auf den anerkannten Anklagesachverhalt das am 1. Januar 2019 in Kraft getretene Ausländer- und Integrationsgesetz (AIG) anwandte und A._ gemäss Art. 119 Abs. 1 i.V.m. Art. 74 Abs. 1 und 2 AIG verurteilte.
Das Bezirksgericht nahm an, die Behörden hätten alles Zumutbare und Nötige vorgekehrt. Die Rückführung sei wiederholt am Verhalten von A._ gescheitert. Er habe wissentlich und willentlich falsche Angaben zu seiner Person gemacht und sei offenkundig nicht bereit, freiwillig auszureisen. Eine Freiheitsstrafe könne daher nicht mehr geeignet sein, die Rückführung zu beeinträchtigen. Diese werde sowieso durch ihn aktiv behindert. Die Bestrafung erweise sich auch unter Mitberücksichtigung der EU-Rückführungsrichtlinie als rechtmässig.
C.
Das Obergericht des Kantons Zürich stellte am 18. Oktober 2019 auf Berufung von A._ hin das gegen ihn geführte Verfahren betreffend Missachtung der Ein- und Ausgrenzung im Sinne von Art. 119 Abs. 1 AuG ein.
Das Obergericht entschied, der Anklagesachverhalt sei anerkannt und rechtsgenügend erstellt. A._ habe den Tatbestand der Missachtung der Ein- und Ausgrenzung im Sinne von Art. 119 Abs. 1 AuG erfüllt.
A._ hatte indes weiter geltend gemacht, eine Verurteilung sei mit Blick auf die bundesgerichtliche Rechtsprechung zur Rückführungsrichtlinie erst zulässig, wenn die zuständigen Behörden alles ihnen Zumutbare unternommen hätten, um die Wegweisung zu vollziehen, der Vollzug indessen am Verhalten des Betroffenen scheitere. Das Obergericht nahm an, das nicht abgeschlossene Rückführungsverfahren stehe einer Strafverfolgung entgegen. Das Verfahren sei einzustellen.
D.
Die Oberstaatsanwaltschaft des Kantons Zürich beantragt mit Beschwerde in Strafsachen, das vorinstanzliche Urteil aufzuheben und die Sache an die Vorinstanz zurückzuweisen, eventualiter A._ gemäss Art. 119 Abs. 1 AuG in Verbindung mit Art. 74 Abs. 1 und 2 AuG schuldig zu sprechen und zu bestrafen.
E.
Das Obergericht verzichtete auf eine Stellungnahme.
A._ bringt vor, die Staatsanwaltschaft wäre selbst verpflichtet gewesen, den bedeutsamen Sachverhalt abzuklären. Bereits mit der Einsprache sei die Rückführungsrichtlinie thematisiert worden. Nicht erst das obergerichtliche Urteil habe Anlass geben können, die telefonische Abklärung (unten E. 2.1) als Novum im Sinne von <ref-law> zuzulassen. Das Obergericht sei nicht veranlasst gewesen, weitere Beweise zu erheben. Der Vorwurf sei geradezu rechtsmissbräuchlich. Auch die Migrationsbehörden hätten ihre Möglichkeiten zur Identitätsfeststellung nicht voll ausgeschöpft. Inwiefern das Obergericht bei der Beurteilung des willkürfrei und rechtmässig festgestellten Sachverhalts Bundesrecht verletzt habe, lege die Staatsanwaltschaft nicht dar. Er ersucht um Abweisung der Beschwerde.

Erwägungen:
1.
Die Oberstaatsanwaltschaft (Beschwerdeführerin) ist grundsätzlich ohne Einschränkungen zur Beschwerde berechtigt (Art. 81 Abs. 1 lit. a und lit. b Ziff. 3; <ref-ruling> E. 1.2 S. 68).
2.
2.1. Die Beschwerdeführerin bringt vor, die Vorinstanz begründe die Verfahrenseinstellung damit, dass die Migrationsbehörden im Februar 2018 einen erneuten Identifikationsversuch unternommen hätten, aufgrund des Schreibens der Migrationsbehörden des Kantons Zürich vom 3. September 2018 jedoch Hinweise bestünden, dass die Abklärungen zur Herkunft des Beschwerdegegners nach wie vor pendent seien und es entsprechend nicht als erstellt erachtet werden könne, dass das verwaltungsrechtliche Rückführungsverfahren abgeschlossen sei. Das nehme die Vorinstanz gestützt auf ein einjähriges Schreiben an. Sie hätte gemäss <ref-law> von Amtes wegen Beweise erheben müssen und verletze den Untersuchungsgrundsatz. Nach telefonischer Rücksprache der Beschwerdeführerin mit der Sachbearbeiterin des SEM sei die Identitätskontrolle abgeschlossen gewesen, was die Sachbearbeiterin mit den Schreiben vom 30. Oktober 2018 und 7. November 2018 dem Migrationsamt des Kantons Zürich mitgeteilt habe. Diese telefonische Abklärung habe das vorinstanzliche Urteil im Sinne von <ref-law> erst veranlasst. Nur mit einer solchen Beweiserhebung hätte die Vorinstanz beurteilen können, ob alles Zumutbare vorgekehrt worden sei und der Vollzug nur am Verhalten des Beschwerdegegners scheitere (Urteil 6B_139/2014 vom 5. August 2014 E. 2). Überdies frage sich, ob eine strafrechtliche Sanktion diese Identitätsabklärung bzw. das pendente Abklärungsverfahren überhaupt verzögere oder verhindere (Urteile 6B_618/2012 vom 11. März 2013 E. 1.5; 6B_617/2012 vom 11. März 2013 E. 1.5). Die Vorinstanz begründe nicht, auf welcher Rechtsgrundlage sie das Strafverfahren einstelle.
Der Beschwerdegegner habe durch sein gesamtes Verhalten seit dem Wegweisungsentscheid vom 12. November 2009 wiederholt gegen die hiesigen Vorschriften verstossen. Er sei nicht gewillt, freiwillig zurückzukehren, weigere sich, seine richtigen Personalien anzugeben bzw. die Richtigkeit der angegebenen Personalien zu bestätigen und sei nicht bereit, bei der Beschaffung der erforderlichen Reisepapiere mitzuwirken. Die Zwangsmassnahme im Sinne der Rückführungsrichtlinie habe sich beim Auftrag zur Effektenkontrolle/Durchsuchung elektronischer Datenträger auf Art. 70 Abs. 1 und Art. 98a AuG i.V.m. <ref-law> gestützt. Weitere Massnahmen würden zu keinem Erfolg führen. Der Beschwerdegegner verhindere seit zehn Jahren den Vollzug des Rückkehrentscheids vom 12. November 2009 absichtlich. Die Verurteilung verstosse nicht gegen die Rückführungsrichtlinie.
2.2. Die Vorinstanz führt aus, die Rückführungsrichtlinie räume dem verwaltungsrechtlichen Verfahren den Vorrang ein. Nationale Strafbestimmungen seien nicht ausgeschlossen, wenn im verwaltungsrechtlichen Verfahren alles für den Vollzug der Rückkehrentscheidung Zumutbare vorgekehrt worden sei, dieser am Verhalten des Betroffenen scheitere (Urteil 6B_139/2014 vom 5. August 2014 E. 2) und die Ausreise objektiv möglich sei (Urteil 6B_482/2010 vom 7. Oktober 2010 E. 3.2.2 f.).
Das Migrationsamt habe das Asylgesuch des Beschwerdegegners am 12. November 2009 abgelehnt und die Wegweisung verfügt. Mit der rechtskräftigen Ablehnung der dagegen erhobenen Beschwerde durch das Bundesverwaltungsgericht am 25. November 2009 sei seine Verpflichtung eingetreten, die Schweiz zu verlassen. Dieser Verpflichtung und zahlreichen nachfolgenden Aufforderungen sei er nicht nachgekommen. Er sei am 20. Januar 2010 in Ausschaffungshaft versetzt und nach sechs Monaten entlassen worden. Er sei am 12. Februar 2014 auf das Gemeindegebiet Adliswil eingegrenzt worden; diese Eingrenzung sei am 15. Oktober 2014 aufgehoben worden. Er sei am 15. September 2016 für zwei Jahre auf das Gebiet der Gemeinde Lindau eingegrenzt worden. Diese Eingrenzung sei am 15. September 2017 auf das Gebiet der Gemeinde Urdorf ausgedehnt worden. Aufgrund seiner Weigerung, seine Herkunft offen zu legen, hätten die Migrationsbehörden diverse Abklärungsversuche betreffend Litauen, Weissrussland und Armenien unternommen, die allesamt erfolglos geblieben seien. Am 31. Januar 2018 habe das Migrationsamt der Kantonspolizei Zürich den Auftrag zur Durchführung einer Effektenkontrolle und zur Auswertung des Mobiltelefons und des Laptops erteilt. Daraus habe sich der Verdacht ergeben, dass er nicht wie behauptet aus Litauen, sondern aus der Ukraine stammen könnte. Diese Daten seien dem SEM zur Auswertung und weiteren Recherche weitergeleitet worden. Gemäss dessen Schreiben vom 3. September 2018 seien die Identitätsabklärungen zum damaligen Zeitpunkt noch pendent gewesen. Es könne nicht als erstellt erachtet werden, dass das verwaltungsrechtliche Rückführungsverfahren abgeschlossen sei.
2.3.
2.3.1. Die Schweiz ist über das Schengen-Abkommen (SR 0.362.31) verpflichtet, die EU-Rückführungsrichtlinie vom 16. Dezember 2008 (RL 2008/115/EU [vormals: EG]) anzuwenden. Diese Richtlinie bezweckt eine minimale Harmonisierung der Verfahren zur Wegweisung und Rückführung von sich illegal aufhaltenden Drittstaatsangehörigen (<ref-ruling> E. 1.2 S. 251, in: Pra 2018 Nr. 78 S. 651). Die Rückführungsrichtlinie ordnet das Rückführungsverfahren verhältnismässig abgestuft mit Vorrang der freiwilligen Ausreise bis zum "letzten Mittel" der Zwangsmassnahmen zur Durchführung der Abschiebung von Widerstand leistenden Drittstaatsangehörigen (Urteil 2C_1063/2019 vom 17. Januar 2020 E. 5 ff. zur Ausschaffungshaft). Die Richtlinie steht der Bestrafung wegen illegalen Aufenthalts nicht entgegen; eine Bestrafung darf aber die effektive Rückführung nicht gefährden (<ref-ruling> E. 1.4.3 S. 254, E. 1.5 S. 256 und E. 1.9 S. 261). Eine Freiheitsstrafe ist daher mit der Richtlinie nur unter der Bedingung vereinbar, dass die Person einer Zwangsmassnahme im Sinne von Art. 8 der Richtlinie unterworfen wurde; darunter ist jede Massnahme zu verstehen, die effektiv und verhältnismässig zur Rückführung der Person nach dem Recht des Mitgliedstaats führt (<ref-ruling> E. 1.3 S. 253, E. 1.5 S. 256 und E. 3.1 S. 261 f.).
2.3.2. Der Empfehlung (EU) 2017/2338 der Kommission vom 16. November 2017 für ein gemeinsames "Rückkehr-Handbuch", das von den zuständigen Behörden der Mitgliedstaaten bei der Durchführung rückkehrbezogener Aufgaben heranzuziehen ist (nachfolgend: HB), lässt sich u.a. entnehmen:
Den Mitgliedstaaten ist es nicht gestattet, den illegalen Aufenthalt von Drittstaatsangehörigen in ihrem Hoheitsgebiet zu tolerieren, ohne entweder ein Rückkehrverfahren einzuleiten oder eine Aufenthaltsberechtigung zu erteilen (HB Rn. 5). Es besteht keine Pflicht zur Ausstellung eines Aufenthaltstitels für nicht rückführbare Personen (HB Rn. 13.2). Der EuGH legt den Begriff der fehlenden hinreichenden Aussicht auf Abschiebung dahingehend aus, dass "nur eine tatsächliche Aussicht auf erfolgreichen Vollzug der Abschiebung unter Berücksichtigung der in Art. 15 Abs. 5 und 6 festgelegten Zeiträume eine hinreichende Aussicht auf Abschiebung darstellt" (HB Rn. 14.4.1).
Nach Entscheidungen des EuGH steht es den Mitgliedstaaten frei, wirksame, verhältnismässige und abschreckende Sanktionen festzulegen, darunter Freiheitsentzug als strafrechtliche Sanktion bei Verstössen gegen die Migrationsbestimmungen, sofern diese Massnahmen nicht die Anwendung der Rückführungsrichtlinie beeinträchtigen und sofern sie die uneingeschränkte Achtung der Grundrechte gewährleisten. Die Rückführungsrichtlinie steht strafrechtlichen Sanktionen nicht entgegen, die nach den nationalen strafverfahrensrechtlichen Vorschriften gegen Drittstaatsangehörige verhängt werden, auf die das mit dieser Richtlinie geschaffene Rückkehrverfahren angewandt wurde und die sich ohne einen Rechtfertigungsgrund für ihre Nichtrückkehr illegal im Hoheitsgebiet eines Mitgliedstaats aufhalten. Die Mitgliedstaaten dürfen nicht vor oder während Rückkehrverfahren allein wegen illegalen Aufenthalts eine Haftstrafe nach nationalem Strafrecht verhängen, da dies die Rückkehr verzögern würde. "Nicht berechtigte Gründe für die Nichtrückkehr" können nach der Auslegung des EuGH Gründe innerhalb des Einflussbereichs des Rückzuführenden sein, die durch das Unionsrecht und das nationale Recht nicht als rechtmässig oder berechtigt anerkannt werden, wie etwa mangelnde Kooperation bei der Beschaffung der Reisedokumente, mangelnde Kooperation bei der Offenlegung der Identität, Vernichtung von Dokumenten, Flucht oder Behinderung der Abschiebung (HB Rn. 4).
2.3.3. Diese Auslegung der Rückführungsrichtlinie wurde mit dem novellierten AIG in das schweizerische Recht integriert (vgl. Botschaft vom 2. März 2018 zur Revision des Ausländergesetzes [AuG; Verfahrensnormen und Informationssysteme], BBl 2018 1685 1694 f. und 1752 f.). Die seit 1. Juni 2019 in Kraft gesetzten Art. 115 Abs. 4-6 AIG (in der Fassung AS 2019 1413 1424) koordinieren das Strafverfahren mit dem Aus- und Wegweisungsverfahren. Die Abs. 4 und 5 (Sistierung des Strafverfahrens [Abs. 4] oder Absehen von der Strafverfolgung, der Überweisung an das Gericht oder der Bestrafung, die einem unmittelbar bevorstehenden Vollzug einer rechtskräftigen Weg- oder Ausweisung entgegensteht [Abs. 5]), gelten nicht, wenn eine Weg- oder Ausweisung aufgrund des Verhaltens der betroffenen Person nicht vollzogen werden konnte (Abs. 6).
2.3.4. Zusammengefasst hindert die Rückführungsrichtlinie nicht, den illegalen Aufenthalt unter Strafe zu stellen, das Rückkehrverfahren geht aber der Bestrafung vor. Wenn auch eine Zwangsmassnahme die Rückführung nicht ermöglicht hat, ist eine Bestrafung wegen illegalen Aufenthalts wieder zulässig. Ist mithin eine zwangsweise Rückschaffung nicht möglich, steht der strafrechtlichen Sanktionierung nichts entgegen; Durchsetzungshaft muss zuvor nicht angeordnet werden (ANDREAS ZÜND, in Migrationsrecht, Marc Spescha et al. [Hrsg.], 5. Aufl. 2019, N. 12 zu <ref-law>).
2.4.
2.4.1. Den Beschwerdegegner trifft ausländerrechtlich eine Mitwirkungspflicht (Art. 90 lit. a-c AIG). Er muss insbesondere zutreffende und vollständige Angaben über die für die Regelung des Aufenthalts wesentlichen Tatsachen machen (lit. a), die erforderlichen Beweismittel unverzüglich einreichen oder sich darum bemühen, sie innerhalb einer angemessenen Frist zu beschaffen (lit. b), die Ausweispapiere beschaffen oder bei deren Beschaffung durch die Behörden mitwirken (lit. c; vgl. Urteil 2C_296/2019 vom 31. Juli 2019 E. 3.1 f.). Der Untersuchungsgrundsatz wird durch die Mitwirkungspflichten des Ausländers relativiert (Urteil 2C_746/2018 vom 11. März 2019 E. 3.3).
2.4.2. Die Argumentation des Beschwerdegegners (Sachverhalt E) vermag bereits angesichts des vorinstanzlich festgestellten Sachverhalts nicht durchzudringen, so dass die Zulässigkeit des Novums im Sinne von <ref-law> (vgl. <ref-ruling> E. 1.2 S. 22 f.) letztlich offen bleiben kann. Die Vorinstanz entschied abweichend vom erstinstanzlichen Urteil. Sie wäre gehalten gewesen, den Sachverhalt so festzustellen, wie er sich zum Zeitpunkt ihres Urteils tatsächlich präsentierte; sie durfte angesichts des aktenkundigen Verhaltens und der zahlreichen erfolglosen Identitätsabklärungen der Behörden nicht schlicht auf ein überjähriges Schreiben vom 3. September 2018 betreffend eine zum damaligen Zeitpunkt noch pendente Identitätsabklärung abstellen (vgl. Urteil 2C_728/2014 vom 3. Juni 2015 E. 2.2.3). Bundesgerichtliche Vorinstanzen sind entsprechend <ref-law> gehalten, den Sachverhalt so festzustellen, wie er sich zum Zeitpunkt ihres Urteils tatsächlich präsentiert (Urteil 6B_378/2018 vom 22. Mai 2019 E. 4.2 mit Hinweisen, nicht publ. in <ref-ruling>).
2.4.3. Es sind zahlreiche Identitätskontrollen und Zwangsmassnahmen durchgeführt worden. Um solche Zwangsmassnahmen im Sinne der Rückführungsrichtlinie handelt es sich insbesondere bei der Ausschaffungshaft, den Eingrenzungen (vgl. <ref-ruling> E. 2.1 S. 18) und der Effektenkontrolle (oben E. 2.2) zwecks Durchsetzung der Ausreise. Der Beschwerdegegner handelte vollauf in Kenntnis der Sachlage und hat sich in seiner Verweigerungshaltung eingerichtet. Er hält sich ohne Rechtfertigungsgrund seit über einem Jahrzehnt illegal im Hoheitsgebiet der Schweiz auf, und zwar aufgrund von innerhalb des Einflussbereichs des Rückzuführenden liegenden "nicht berechtigten Gründen für die Nichtrückkehr"; aktuell ist keine "hinreichende Aussicht auf Abschiebung" erkennbar (vgl. oben E. 2.3.2).
Es ist vorinstanzlich nicht begründet, inwiefern ein Freiheitsentzug die Anwendung der Rückführungsrichtlinie beeinträchtigen sollte. Die Vorinstanz wird den massgebenden Sachverhalt (<ref-law>) im Urteilszeitpunkt festzustellen und aufgrund dieser Feststellungen neu zu entscheiden haben.
3.
Die Beschwerde ist gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen (<ref-law>; <ref-ruling> E. 5.2.1 S. 220 und E. 5.3.3 S. 222 f.). Das Gesuch um unentgeltliche Rechtspflege ist gutzuheissen. Der Anwalt des Beschwerdegegners ist aus der Bundesgerichtskasse für das Vernehmlassungsverfahren zu entschädigen (<ref-law>). Es sind keine Kosten aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Obergerichts des Kantons Zürich vom 18. Oktober 2019 wird aufgehoben und die Sache zu neuer Beurteilung an die Vorinstanz zurückgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen.
3.
Es werden keine Kosten erhoben.
4.
Rechtsanwalt Nicolas von Wartburg wird aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
5.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 11. März 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Briw