Simple: you will need to contact your home country's embassy/consulate in the country you are staying at, and they will issue you a travel document to be used to pass to your country.
The country in which you are staying can not issue you a passport (unless you are a refugee or stateless or something like that), when the passport is lost, the maximum the host country can do is issuing some sort of a report via a police station stating that you have lose your passport. The rest has to be done via the consulate/embassy.
For the visa, you will need to issue a new one. Unless the visa is not attached to the passport and it is in a separate card or so. You also most likely will have to re-issue it from your country as most consulates will issue you a single use travel document (in case you needed to get back quickly), this can not be used to issue visas. In case your consulate issued you a full passport, not much countries will issue you a visa while you are in the country, you will need to get back. Unless it is a long term visa, things tend to be different in these cases.